Computer Science/Discrete Mathematics Seminar I

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 good list-decodability, but we do not know many structural conditions on a code which guarantee 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 near-optimally list-decodable, with high probability. As corollaries we settle two long-standing open questions, showing that (1) random linear codes are (nearly) 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.