Earlier this month, the Simons Institute convened a group of theoretical computer scientists from academia and industry to develop a set of...
Greetings from Berkeley, where our fall research programs on Spectral Theory Beyond Graphs, and on Pseudorandomness & High-Dimensional Expansion are...
This month, we sat down for a conversation with the newest member of our leadership team, Senior Scientist Jason Lee. Jason is an Associate Professor...
High-dimensional expansion (HDX) is a generalization of expansion in graphs to higher dimensions (i.e., hypergraphs). In this first of three lectures from our ICM satellite conference, Mitali Bafna defines the spectral notion of HDX, proves the trickle-down theorem, and defines random walks on HDX.
Eugenia Sapir’s mini-course provides an introduction to hyperbolic surfaces, including their basic topology and (hyperbolic) geometry, several random models for surfaces (some of which are directly defined using random graphs), and the ways in which many results about random surfaces parallel those for random graphs.
In this presentation from this fall’s joint boot camp for the programs on Spectral Theory Beyond Graphs and on Pseudorandomness & High-Dimensional Expansion, William Hoza presents an introduction to the “L vs. BPL” problem, which asks whether randomness is ever necessary for space-efficient computation.
We present here the first part of Jorge Garza-Vargas’s three-part mini-course on the strong convergence phenomenon, from our ICM Satellite Conference on Spectral Theory, High-Dimensional Expansion, and Pseudorandomness. The course introduces and motivates the notion of strong convergence, discusses recent proof techniques, and showcases concrete applications.
Earlier this month, the Simons Institute convened a group of theoretical computer scientists from academia and industry to develop a set of recommendations for how this research community should respond to the increasing power and influence of AI. Their report, “AI and TCS: The Next Six Months,” was released this Monday.
Greetings from Berkeley, where our fall research programs on Spectral Theory Beyond Graphs, and on Pseudorandomness & High-Dimensional Expansion are in full swing. The Simons Institute has been hopping this past month, with workshops during four of the last five weeks: our ICM Satellite Conference on Spectral Theory, High-Dimensional Expansion, and Pseudorandomness; a joint boot camp for our two fall programs; a reunion of the Fall 2025 program on Algorithmic Foundations for Emerging Computing Technologies; and the first thematic workshops of each of the programs.
Louis Golowich (UC Berkeley) shows how to perform classical and quantum computation in the presence of an almost-linear number of adversarial errors in every time step, and the utility of such schemes toward PCP constructions, both classical and quantum.
Fan Chen (MIT) presents an algorithmic framework for high-accuracy sampling using unbiased stochastic queries.
Shankar Balasubramanian (Caltech) presents research constructing a 3D Pauli stabilizer Hamiltonian whose ground-state space can encode a qubit for exponential time when coupled to a bath at nonzero temperature.
Hsin-Yuan (Robert) Huang asks whether there is a path forward for working with LLMs in a way that does not undermine the sacred human act of doing research.