Max Hopkins (Princeton)- As Hard as it Gets: Hardness Amplification and Local List Decoding from HDX
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
Speakers
Max Hopkins
Max Hopkins received his PhD in 2024 from UC San Diego, supported in part by an NSF GRFP Fellowship. He currently resides as a postdoctoral scholar at the Institute for Advanced Study and Princeton University. Max is broadly interested in the role of structure and randomness in computation, especially with respect to high-dimensional expansion and geometric structure in learning.
