Talks

We will talk about a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. These constructions often proceed by showing that the distance of local constant-sized codes can be lifted to a distance lower bound for the global code. The regularity framework allows us to similarly lift list size bounds for local base codes, to list size bounds for the global codes.

This allows us to obtain novel combinatorial bounds for list decoding and list recovery up to optimal radius, for Tanner codes of Sipser and Spielman, and for the distance amplification scheme of Alon, Edmonds, and Luby. Further, using existing algorithms for computing weak-regularity decompositions of sparse graphs in (randomized) near-linear time, these tasks can be performed in near-linear time.

Based on joint work with Madhur Tulsiani.
DIMACS (Rutgers University) and Institute for Advanced 

We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of O(1/ϵ). In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs.

Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS'95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a "local-to-global" phenomenon for (a slight strengthening of) the generalized Singleton bound.

As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound.

Based on joint work with Fernando Granha Jeronimo, Tushant Mittal, and Shashank Srivastava.

The theory of probabilistically checkable proofs (PCPs) shows how to encode a proof for any theorem into a format where the theorem's correctness can be verified by making only a constant number of queries to the proof. The PCP Theorem [ALMSS] is a fundamental result in computer science with far-reaching consequences in hardness of approximation, cryptography, and cloud computing. A PCP has two important parameters: 1) the size of the encoding, and 2) soundness, which is the probability that the verifier accepts an incorrect proof, both of which we wish to minimize. In 2005, Dinur gave a surprisingly elementary and purely combinatorial proof of the PCP theorem that relies only on tools such as graph expansion, while also giving the first construction of 2-query PCPs with quasi-linear size and constant soundness (close to 1). Our work improves upon Dinur's PCP and constructs 2-query, quasi-linear size PCPs with arbitrarily small constant soundness. As a direct consequence, assuming the exponential time hypothesis, we get that no approximation algorithm for 3-SAT can achieve an approximation ratio significantly better than 7/8 in time 2^{n/polylog n}. In this talk, I will introduce PCPs and discuss the components that go into our proof. This talk is based on joint work with Dor Minzer and Nikhil Vyas, with an appendix by Zhiwei Yun.

GAP codes are error-correcting codes based on evaluating degree-d m-variate polynomials at some
geometrically arranged points in F_q^m. For m constant and any epsilon > 0, these codes can achieve rate 1-epsilon and distance Omega(1).
For Reed-Muller codes, where the evaluation points form all of F_q^m, the rate is is exponentially small in $m$.

GAP codes turn out to have a a very simple description from the point of view of HDXs: they are Tanner codes on the complete $m$-dimensional complex with Reed-Solomon codes as the inner code.

I will talk about their construction, how to decode them, and the somewhat surprising fact that despite having much fewer evaluation points than Reed-Muller codes, GAP codes are also locally testable with O(n^{1/m}) queries.

Joint work with Harry Sha and Mrinal Kumar
(Based on part of this paper: https://arxiv.org/abs/2410.13470 )

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