In the theory of error-correcting codes, list decoding is a relaxation of unique decoding useful for tolerating higher levels of noise. Design of list decoding algorithms for algebraic codes, such as Reed-Solomon, has found numerous applications in error correction, as well as in complexity theory and pseudorandomnness. However, we know of very few techniques for list decoding algorithms when the code may not have such algebraic structure, such as Tanner codes which are defined using sparse expander graphs.
In this talk, I will describe how continuous relaxations based on the Sum-of-Squares hierarchy can be used to design the first list decoding algorithm for Tanner codes of Sipser-Spielman [IEEE Trans. Inf. Theory 1996]. The techniques include a novel proof of the Johnson bound for arbitrary codes, distance proofs for pseudocodewords, and correlation rounding for convex hierarchies. I will also discuss extensions to a distance amplification scheme of Alon-Edmonds-Luby [FOCS 1995].
Based on joint work with Fernando Granha Jeronimo and Madhur Tulsiani.
