Talks
Spring 2017

(Yet More) List-Decodability of Random Linear Codes

Thursday, February 2nd, 2017, 2:00 pm2:45 pm

Add to Calendar

Location: 

Calvin Lab Auditorium

In error-correcting codes, list-decoding (and related properties) are intimately related to pseudorandom objects like expanders and extractors.  As with many pseudorandom notions, list-decodability is not well-understood: It's easy to see that completely random codes have excellent list-decodability properties, and we have some very nice explicit constructions, but we still don't really understand this for many families of codes that we know and love.  One example is random linear codes; this has been well-studied, especially in the past few years, but there are still gaps in our knowledge.  In this talk, I'll discuss some recent work with Atri Rudra about the (average-radius) list decodability (and recovery) of random linear codes; along the way I'll highlight connections to and applications in expanders and extractors.