List decodability of randomly punctured codes

Computer Science/Discrete Mathematics Seminar I
Topic:List decodability of randomly punctured codes
Speaker:Mary Wootters
Affiliation:University of Michigan
Date:Monday, March 24
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2014/0324-MaryWootters

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.