Seminar Details
As Hard as it Gets: Hardness Amplification and Local List Decoding from HDX
- Start Date: February 4, 2026
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Max Hopkins - Institute for Advanced Study
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Presentation Type: Stand Alone Presentation
- Abstract:
Can we encode data in a way that is recoverable even when 1) most data becomes corrupted, and 2) we can only read a sub-constant fraction of the database? This is the central question of local list decoding, a powerful tool from coding theory central to interactive proofs, hardness amplification, and pseudorandomness. In this talk we overview the first construction of high rate (approximate) locally list decodable codes with error tolerance and efficiency approaching the information theoretic limit, along with their application to longstanding problems including:
- Near-optimal hardness amplification and pseudorandom generators
- Good codes with fast parallel list decoding (RNC^1)
- Rate and locality preserving distance amplification
Finally, we overview our decoding algorithm: a new belief propagation framework for the powerful class of high dimensional expanders based on a primitive we call (fault-tolerant) strongly explicit routing, a polylogarithmic time algorithm computing short random paths between arbitrary vertices of a graph G.
Based on joint work with Yotam Dikstein, Russell Impagliazzo, and Toniann Pitassi