List decodability of randomly punctured codes

We consider the problem of the list-decodability of error correcting codes. The well-known Johnson bound implies that any code with good distance has "decent" list-decodability, but we do not know many structural conditions on a code which guarantee *good* list-decodability (beyond the Johnson bound). We provide a randomized result of this type, and we show that random puncturings of codes with good distance are list-decodable well beyond the Johnson bound, with high probability. As corollaries we settle two long-standing open questions, showing that (1) random linear codes are optimally list-decodable, and that (2) there exist Reed-Solomon codes which are list-decodable beyond the Johnson bound. This is joint work with Atri Rudra.