Talks

Chernoff's bound states that for any $A \subset [N]$ the probability a random $k$-tuple $s \in {[N] \choose k}$ correctly `samples' $A$ (i.e. that the density of $A$ in $s$ is close to its mean) decays exponentially in the dimension $k$. In 1987, Ajtai, Komlos, and Szemeredi proved the "Expander-Chernoff Theorem", a powerful derandomization of Chernoff's bound stating that one can replace ${[N] \choose k}$ with the significantly sparser family $X_G(k) \subsetneq {[N] \choose k}$ of length-$k$ paths on an expander graph $G$ while maintaining essentially the same concentration. Their result, which allows amplification without significant blow-up in size or randomness, has since become a mainstay in theoretical computer science with breakthrough applications in derandomization, coding, pseudorandomness, cryptography, and complexity.

One natural way to view AKS is to say Expander-Walks are pseudorandom with respect to functions of their vertices, or against "degree 1" functions. In modern complexity, especially in the context of hardness amplification and PCPs, we often need concentration against higher degree functions, e.g. functions of edges or triples. Unfortunately, due to their inherent low-dimensionality, walks on expanders are not pseudorandom even at degree 2, and the construction of such a de-randomized object has remained largely open. 

In 2017 Dinur and Kaufman offered a partial resolution to this question in high dimensional expanders, a derandomized family satisfying Chebyshev-type (inverse polynomial) concentration for higher degree functions. Their work led to breakthrough applications in agreement testing and PCPs (Bafna, Minzer, Vyas, and Yun STOC 2025), but left an exponential gap with known bounds for the complete hypergraph ${[N] \choose k}$ needed for further applications. In this talk, we close this gap and prove (strong enough) HDX indeed have Chernoff-type tails. Time willing, we will discuss the relation of these bounds to a powerful analytic inequality called reverse hypercontractivity and its applications to agreement tests with optimal soundness.

Based on joint work with Yotam Dikstein.
 

Rydberg atom arrays have emerged as powerful quantum simulators, capable of preparing strongly correlated phases of matter that are potentially challenging to access with classical computational methods. A major focus has been on realizing these arrays on frustrated geometries, aiming to stabilize exotic many-body states like spin liquids. In this talk, I will show how two-dimensional recurrent neural network (RNN) wave functions can be used to study the ground states of Rydberg atom arrays on the kagome lattice. For Hamiltonians previously investigated in this geometry, I will demonstrate that the RNN finds no evidence for exotic spin liquid phases or emergent glassiness. In particular, I will argue that signals of glassy behavior, such as a nonzero Edwards-Anderson order parameter seen in quantum Monte Carlo (QMC) studies, may arise from artifacts related to long autocorrelation times. These results highlight the potential of language model-inspired approaches, like RNNs, for advancing the study of frustrated quantum systems and Rydberg atom physics more broadly.

arXiv paper: https://arxiv.org/pdf/2405.20384

Einstein's theory admits interesting limits with different causal structures obtained by letting the speed of light go to infinity (Galilean or "non-relativistic" limit) or to zero (Carrollian, sometimes called "ultrarelativistic", limit). The Carroll limit turns out to be relevant near spacelike (cosmological) singularities, and particularly so when p-form gauge fields are coupled to gravity as in the context of extended supergravities. The resulting differential equations possess a remarkable interpretation in terms of infinite-dimensional Kac-Moody algebras. The talk will review various aspects of Carroll invariant theories, of the Belinski-Khalatnikov-Lifshitz analysis of spacelike singularities and of the related symmetries.