Tata Institute of Fundamental Research

List Decoding of Tanner and Expander Amplified Codes from Distance Certificates

STCS Seminar
Speaker: Mr. Shashank Srivastava (Toyota Technological Institute at Chicago (TTIC))
Organiser: Prahladh Harsha
Date: Thursday, 4 Jan 2024, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
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.