Computer Science/Discrete Mathematics Seminar II
10:30am|Simonyi 101 and Remote Access
Topic: Explicit Codes Approaching the Generalized Singleton Bound Using Expanders
Speaker: Shashank Srivastava
Affiliation: Institute for Advanced Study
Date: January 21, 2025
Error correcting codes are objects designed to withstand errors that may arise during communication. Originally intended for practical use, codes have come to be established as one of the central objects of study in theoretical computer science, due to their connections to complexity theory and pseudorandomness.
A code is said to achieve list decoding capacity if it can tolerate information theoretically optimal amount of adversarial corruption. Such codes have been known to exist via the probabilistic method, and a long line of work has shown that the folded Reed-Solomon codes, and several of their variants, are explicit codes with such a property. However, all of these constructions rely heavily on finite field algebra, and in particular use polynomial interpolation based machinery pioneered by Guruswami and Sudan in late 90s.
In this talk, we will show how to construct explicit list decoding capacity achieving codes using just spectral expanders, without relying on algebraic ingredients. In fact, these codes approach the generalized Singleton bound, which implies optimal list sizes, making them the first explicit family of codes to do so over constant sized alphabet. Further, our construction is based on a standard distance amplification scheme of Alon, Edmonds and Luby [FOCS’95], and is flexible enough to support properties such as LDPC and linear time unique decodability. The proof can be seen as a local-to-global phenomenon for the generalized Singleton bound, and utilizes simple combinatorial properties of expander graphs.
Based on joint work with Fernando Granha Jeronimo, Tushant Mittal and Madhur Tulsiani.