|Computer Science/Discrete Mathematics Seminar I|
|Topic:||List decodability of randomly punctured codes|
|Affiliation:||University of Michigan|
|Date:||Monday, March 24|
|Time/Room:||11:15am - 12:15pm/S-101|
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.