Boolean functions are perhaps the most basic objects of study in theoretical computer
science. They also arise in other areas of mathematics, including combinatorics, statistical …

A basic fact in spectral graph theory is that the number of connected components in an
undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of …

We study the problem of learning a local quantum Hamiltonian H given copies of its Gibbs
state ρ= e− β H/(e− β H) at a known inverse temperature β> 0. Anshu, Arunachalam …

Outlier-robust estimation is a fundamental problem and has been extensively investigated
by statisticians and practitioners. The last few years have seen a convergence across …

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion.
This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit …

We study the problem of algorithmically optimizing the Hamiltonian HN H_N of a spherical or
Ising mixed pp‐spin glass. The maximum asymptotic value OPT OPT of HN/N H_N/N is …

We develop efficient algorithms for estimating low-degree moments of unknown distributions
in the presence of adversarial outliers and design a new family of convex relaxations for k …

We study planted problems-finding hidden structures in random noisy inputs-through the
lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of …

We prove that with high probability over the choice of a random graph G from the Erdös--
Rényi distribution G(n,1/2), the n^O(d)-time degree d sum-of-squares (SOS) semidefinite …

Optimization of mean-field spin glasses Page 1 The Annals of Probability 2021, Vol. 49, No. 6,
2922–2960 https://doi.org/10.1214/21-AOP1519 © Institute of Mathematical Statistics, 2021 …