Abstract
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.