EECS Special Seminar: Max Hopkins, “Fast Codes and Hard Functions: Derandomization from High Dimensional Expanders”

Abstract: 
Pseudorandomness and derandomization are central themes in the study of computation, underlying everything from the ubiquitous theory of error-correcting codes to modern cryptographic protocols and the fundamental limits of efficient computing. In this talk, I will give an overview of my work in derandomization, focusing on the resolution of several longstanding problems in the quest for faster error correction and computationally hard problems, through the development of the powerful theory of /high dimensional expanders /(HDX)/, /a new, broadly applicable pseudorandomness primitive generalizing the classical theory of expander graphs. 

Concretely, in this talk I will present the first construction of good codes with fast parallel decoders from extreme noise, the first optimal hardness amplification theorem, and discuss both problems’ underlying connection to pseudorandomness. I will discuss their resolution through my work developing high dimensional expanders as a theory of pseudo-independent distributions (generalizing core tools like Chernoff’s bound), and touch on the broader impact of these methods across computer science from quantum computation to super-efficient probabilistically checkable proofs.

Bio:
Max Hopkins is a postdoctoral member at the Institute for Advanced Study. Prior to this, he spent a year as a postdoctoral associate at Princeton University, and completed his PhD at UC San Diego funded in part by NSF GRFP, ARCS, and Simons Research Fellowships. Max is broadly interested in the theory of computing, focused primarily on computational complexity, pseudorandomness, learning, and algorithmic stability.

Details

• Date: Wednesday, March 18
• Time: 11:00 am - 12:00 pm
• Location: 34-401 Grier A

Host

• Yael Kalai
• Email: fern@csail.mit.edu