Pseudorandomness & High-Dimensional Expansion

Pseudorandomness is the theory of efficiently generating random-like objects using little or no randomness. Defining “random-like” in different ways gives different notions of pseudorandomness that have been useful in a variety of different areas of computer science and mathematics. Such areas extend well beyond the original motivation of derandomization, and include computational complexity, algorithms, cryptography, communication, and combinatorics. The main objects of study are pseudorandom generators of various kinds, randomness extractors, expander graphs, and error-correcting codes. Pseudorandomness has been a subfield of theoretical computer science for over four decades, and there continues to be progress on fundamental open questions.  Examples of such questions include the unconditional derandomization of space-bounded computation (BPL=L), identification of hardness assumptions that are equivalent to polynomial-time derandomization (BPP=P), derandomization with minimal overhead in runtime, and the construction of near-optimal vertex expanders and two-source randomness extractors.

High-Dimensional Expansion (HDX) is a generalization of expansion in graphs to higher dimensions (i.e. hypergraphs), as captured by the relatively new and very powerful definitions of local spectral expansion and coboundary expansion. These notions differ from typical notions of pseudorandomness in that sparse random hypergraphs fail miserably in satisfying them. Still, the relation to pseudorandomness is apparent when comparing to dense, rather than sparse, objects.  Despite being at an early stage of research, high-dimensional expansion has already been at the heart of a number of breakthrough results in other areas, such as error-correcting codes (yielding the first constructions of asymptotically good locally testable codes and quantum LDPC codes), bounding the mixing time of Markov chains (leading to the first polynomial-time algorithm for sampling bases of matroid), PCPs (the first quasi-linear-sized PCPs with small soundness error), and the aforementioned construction of graphs with near-optimal vertex expansion. 

The Pseudorandomness and High-Dimensional Expansion program seeks to make advances on the fundamental problems within the areas, strengthen the ties between the two communities (and thereby grow the HDX community), and advance applications to and connections with other areas (including Spectral Theory, as represented in a concurrent program at the Simons Institute).

Long-Term Participants (tentative): Eshan Chattopadhyay (Cornell University), Lijie Chen (UC Berkeley), Gil Cohen (Tel Aviv University), Irit Dinur (Weizmann and IAS), Dean Doron (Ben-Gurion University), Shai Evra (Hebrew University), Venkat Guruswami (UC Berkeley), Prahladh Harsha (TIFR, Mumbai), Shuichi Hirahara (National Institute of Informatics), Russell Impagliazzo (UC San Diego), Tali Kaufman (Bar Ilan University), Xin Li (Johns Hopkins), Shachar Lovett (UC San Diego), Raghu Meka (UCLA), Dor Minzer (MIT), Dana Moshkovitz (UT Austin), Izhar Oppenheim (Ben Gurion University), Omer Reingold (Stanford University), Noga Ron-Zewi (University of Haifa), Ronen Shaltiel (University of Haifa), Avishay Tal (UC Berkeley), Amnon Ta-Shma (Tel Aviv University), Roei Tell (University of Toronto), Salil Vadhan (Harvard University), Emanuele Viola (Northeastern University), Avi Wigderson (IAS), David Zuckerman (UT Austin)