List decodability of structured ensembles of random codes
October 1, 2014

In the unique decoding problem, Alice wants to talk to Bob over a noisy channel, and Bob's job is to figure out (exactly) what Alice meant to say. List-decoding is a relaxation of this model, where Bob is allowed to return a short list of messages, with the guarantee that Alice's true message is in the list somewhere. In addition to helping Alice and Bob communicate, list-decoding has applications throughout complexity theory. In this talk, we'll investigate the list-decodability of some random ensembles of codes. The (very informal) punchline is that any "reasonable" distribution on codes with enough randomness is nearly optimally list-decodable with high probability. In the talk we'll make this punchline slightly more precise; as corollaries, we'll establish the list-decodability of random linear codes for high error rates, and the existence of Reed-Solomon codes that are nearly optimally list-decodable. Our arguments apply more generally to random modifications (folding, puncturing, etc) of "good enough" codes.

This is joint work with Atri Rudra.