Computer Science/Discrete Mathematics Seminar I

The ABNNR encoding is a classical encoding scheme that amplifies the distance of an error correcting code. The encoding takes an error correcting code with a small distance and constructs an error correcting code with distance approaching one, by using a bipartite expander graph.

The ABNNR encoding has an efficient decoding algorithm, which can correct a codeword with not too many corrupted coordinates. However, if half or more of the coordinates are corrupted, the decoding algorithm does not work.

In this talk, I'm going to present a list-decoding algorithm for the ABNNR encoding, which can correct a large fraction of errors. In list-decoding, instead of returning a single codeword, the algorithm returns a list of possible codewords that are somewhat close to the input. This is the first list-decoding algorithm for the ABNNR encoding. I am going to give a high-level overview of the algorithm, its requirements, and talk about its correctness.

This is from joint work with Irit Dinur, Prahladh Harsha, Tali Kaufman, and Amnon Ta-Shma.