The problem of optimizing over random structures emerges in many areas of science and
engineering, ranging from statistical physics to machine learning and artificial intelligence …

We consider the Sherrington-Kirkpatrick model of spin glasses at high-temperature and no
external field, and study the problem of sampling from the Gibbs distribution μ in polynomial …

Many high-dimensional statistical inference problems are believed to possess inherent
computational hardness. Various frameworks have been proposed to give rigorous …

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 …

Computational barriers to estimation from low-degree polynomials Page 1 The Annals of
Statistics 2022, Vol. 50, No. 3, 1833–1858 https://doi.org/10.1214/22-AOS2179 © Institute of …

Let Φ be a uniformly random k-SAT formula with n variables and m clauses. We study the
algorithmic task of finding a satisfying assignment of Φ. It is known that satisfying …

We consider Ising mixed $ p $-spin glasses at high-temperature and without external field,
and study the problem of sampling from the Gibbs distribution $\mu $ in polynomial time. We …

The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be
viewed as a random constraint satisfaction problem with a high degree of connectivity. The …

We introduce a notion of\emph {generic local algorithm} which strictly generalizes existing
frameworks of local algorithms such as\emph {factors of iid} by capturing local\emph …

The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic
paradigm which captures state-of-the-art algorithmic guarantees for a wide array of …