Talks

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.

The recent detection of a low frequency gravitational wave background by pulsar timing arrays provides solid evidence that the observable universe contains a population of in-spiralling supermassive black hole binaries. Such binaries likely form as a result of collisions between galaxies and can offer clues as to how black holes and galaxies grow over time. Moreover, since galactic centers are often densely populated by gas and stars, these systems are much more likely to be actively accreting and radiating compared to stellar mass-sized black hole binaries. This makes them promising candidates for multi-messenger detection (combining electromagnetic and gravitational wave information), particularly when LISA comes online or as pulsar timing arrays improve their sensitivity. In order to facilitate this goal, it is important that, in addition to predictions for the possible gravitational wave signals from numerical relativity, we also develop predictions for electromagnetic signals from simulations of black hole binary accretion. In this talk I will present some of our recent results from 3D general relativistic magnetohydrodynamic simulations that utilize a strong-field approximation to the in-spiralling spacetime metric. Specifically, I will showcase several possible distinctive electromagnetic signals from black hole binaries, including quasi-periodic emission, jet precession, and two processes analogous to flaring activity frequently observed in the outer layer of the Sun.

We show that specific exponential integrals serve as generating functions of labeled edge-colored graphs. Based on this, we derive asymptotics for the number of edge-colored graphs with arbitrary weights assigned to different vertex structures. The asymptotic behavior is governed by the critical points of a polynomial. As an application, we discuss the Ising model on a random graph and show how its phase transitions arise from our formula.

We explore the interplay of quantum computing and machine learning to advance experimental protocols for observing measurement-induced phase transitions (MIPT) in quantum devices. In particular, we focus on trapped ion monitored circuits and apply the cross entropy benchmark recently introduced by [Li et al., Phys. Rev. Lett. 130, 220404 (2023)], which can mitigate the postselection problem. By doing so, we reduce the number of projective measurements -- the sample complexity required per random circuit realization, which is a critical limiting resource in real devices. Since these projective measurement outcomes form a classical probability distribution, they are suitable for learning with a standard machine learning generative model. In this work, we use a recurrent neural network (RNN) to learn a representation of the measurement record for a native trapped-ion MIPT, and show that using this generative model can substantially reduce the number of measurements required to accurately estimate the cross entropy. This illustrates the potential of combining quantum computing and machine learning to overcome practical challenges in realizing quantum experiments. 

We look at the stability and sensitivity of planar percolation models generated by a Poisson point process under re-sampling dynamics. Noise stability refers to whether certain global percolation events remain unchanged when a small fraction of points are re-sampled, while noise sensitivity means these events become nearly independent even when only arbitrarily small fraction of points are re-sampled.

To analyze these properties, one wants to estimate chaos coefficients in the Wiener-Itô chaos expansion for Poisson functionals, analogue of Fourier-Walsh expansion for functionals of random bits. Motivated by substantial progress in the case of random bits, we introduce two tools to estimate the chaos coefficients. First approach is via stopping sets, which serve as a continuum analogue of randomized algorithms, and the second approach is using pivotal and spectral samples, which provide sharper bounds.

We illustrate these methods using two well-known models: Poisson Boolean percolation, where unit balls are placed at Poisson points, and Voronoi percolation, where Voronoi cells based on Poisson points are randomly retained. Our focus will be on sharp noise sensitivity or stability of crossing events, specifically whether a large rectangle is traversed by a connected component of the percolation model.

The talk is based on joint projects with Chinmoy Bhattacharjee, Guenter Last, and Giovanni Peccati

In recent years, random graph models with latent geometric structures have received increasing attention. These models typically involve sampling random points from a metric space, followed by independently adding edges with probabilities that depend on the distances between corresponding point pairs. A central computational challenge is to detect the underlying geometry and recover the latent coordinates of the vertices based solely on the observed graph. Unlike classical random graph models, geometric models exhibit richer structural properties, such as correlations between edges. These features make them more realistic representations of real world networks and data. However, our current understanding of the information-theoretic and computational thresholds for detection in these models remains limited. In this talk, we will survey known algorithmic results and computational hardness findings for several random geometric graph models. We will also highlight open directions for future research.

This talk explores how problems in private optimization—specifically, low-rank matrix approximation—give rise to novel tools and results in sampling and statistical physics. I will present two recent advances:

Sampling from Harish-Chandra–Itzykson–Zuber (HCIZ) Distributions via Private Optimization:
We introduce an efficient algorithm for computing private low-rank approximations and show how its structure enables efficient sampling from HCIZ measures, which are central to mathematical physics and random matrix theory.

Spectral Sampling and Utility of the Gaussian Mechanism:
We provide a new analysis of the Gaussian Mechanism for differential privacy through the lens of Dyson Brownian motion, yielding refined spectral sampling guarantees and new bounds on eigenvalue gaps in random matrices.

These results illustrate how sampling tasks arising from privacy constraints can lead to powerful connections between random matrix theory, optimization, sampling, and statistical physics.

Assuming the polynomial hierarchy is infinite, we prove a sufficient condition for determining if uniform and polynomial size quantum circuits over a non-universal gate set are not efficiently classically simulable in the weak multiplicative sense. Our criterion exploits the fact that subgroups of SL(2; C) are essentially either discrete or dense in SL(2; C). Using our criterion, we give a new proof that both instantaneous quantum polynomial (IQP) circuits and conjugated Clifford circuits (CCCs) afford a quantum advantage. We also prove that both commuting CCCs and CCCs over various fragments of the Clifford group afford a quantum advantage, which settles two questions of Bouland, Fitzsimons, and Koh. Our results imply that circuits made of just U \otimes U-conjugated CZ gates afford a quantum advantage for almost all single-qubit unitaries U.

We review the localization method, pioneered by Lov\'asz and Simonovits (1993) and developed substantially by Eldan (2012),  to prove inequalities in high dimension. At its heart, the method uses a sequence of transformations to convert an arbitrary instance to a highly structured one (often even one-dimensional). We will work out some illustrative examples. 

We review the localization method, pioneered by Lov\'asz and Simonovits (1993) and developed substantially by Eldan (2012),  to prove inequalities in high dimension. At its heart, the method uses a sequence of transformations to convert an arbitrary instance to a highly structured one (often even one-dimensional). We will work out some illustrative examples.