TCS+ Online Seminar

List-decodability of Structured Random Codes

In the list-decoding problem, a sender (Alice) sends a message to a receiver (Bob) over a noisy channel, and Bob's job is to come up with a short list of messages with the guarantee that Alice's true message appears in the list. It turns out that Alice and Bob can succeed even when nearly all of the symbols that Alice sends to Bob are corrupted. It is known (and not hard to see) that a completely random code will achieve this, and it is also known (and much harder) that there are explicit codes which achieve this. In this talk, we'll explore the middle-ground of structured random codes: for example, random linear codes, or Reed-Solomon codes with random evaluation points. Our main result is that if you start with any q-ary code with sufficiently good distance and randomly puncture it, then with high probability, you get a code that is list-decodable up to a 1 - 1/q - epsilon fraction of errors, with near-optimal rate and list sizes. Our results imply that "most" Reed-Solomon codes are list-decodable beyond the Johnson bound; whether or not such codes even existed was previously open. Our results also imply improved bounds on the list-decodability of random linear codes over large alphabets. This is joint work with Atri Rudra.