Low-degree hardness of random optimization problems, in particular the maximum independent set problem. The proof has two ingredients: (1) (Multi, Ensemble) Overlap Gap Property and (2) Stability of Low-Degree Polynomials.

Based on arXiv:2004.12063 and arXiv:2010.06563.

We consider the algorithmic problem of finding a near-optimal solution for the number partitioning problem (NPP). This problem appears in many practical applications, including the design of randomized controlled trials, multiprocessor scheduling, and cryptography; and is also of theoretical significance. The NPP possesses the so-called statistical-to-computational gap: when its input has distribution N(0,I_n), the optimal value of NPP is \Theta(2^{-n}) w.h.p.; whereas the best polynomial-time algorithm achieves the objective value of only 2^{-\Theta(\log^2 n)}, w.h.p.

In this work, we initiate the study of the nature of this gap for the NPP. Inspired by insights from statistical physics, we study the landscape of the NPP and establish the presence of the Overlap Gap Property (OGP), an intricate geometric property which is known to be a rigorous evidence of an algorithmic hardness for large classes of algorithms. By leveraging the OGP, we establish that (a) any sufficiently stable algorithm, appropriately defined, fails to find a near-optimal solution with energy below 2^{-\omega(n \log^{-1/5} n)}; and (b) a very natural Markov Chain Monte Carlo dynamics fails for find near-optimal solutions.

OGP regards the overlap structure of m-tuples of solutions achieving a certain objective value. When m is constant, we prove the presence of OGP for the objective values of order 2^{-\Theta(n)}, and the absence of it in the regime 2^{-o(n)}. Interestingly, though, by considering overlaps with growing values of m we prove the presence of the OGP up to the level 2^{-\omega(\sqrt{n\log n})}. Our proof of the failure of stable algorithms at values 2^{-\omega(n \log^{-1/5} n)} employs methods from Ramsey Theory from the extremal combinatorics and is of independent interest.

Based on arXiv:2103.01369. Joint work with David Gamarnik.

The Overlap Gap Property (OGP) is the condition that in a problem's solution space, no two solutions are a medium distance apart. In many random optimization problems with information-computation gaps, OGP has been shown to imply failure of stable algorithms at a threshold well below the existential limit, but still above the algorithmic limit.

A multi-OGP is an enhancement of OGP whose forbidden structure involves several solutions. In several random optimization problems, recent work has shown that an appropriately designed multi-OGP implies failure of stable algorithms at or just beyond the algorithmic limit.

The goal of this talk is to show how to design such a multi-OGP, and to demonstrate the energy computations involved in choosing the forbidden structure. As an illustrative example, we will discuss the multi-OGP for maximum independent set constructed by Alex Wein, which implies optimal hardness against low degree polynomials.

Based on arXiv:2010.06563, "Optimal Low-Degree Hardness of Maximum Independent Set" by Alex Wein.

The Overlap Gap Property (OGP) is an intricate geometric/topological property asserting (in the context of random combinatorial optimization problems) that two nearly optimal solutions are either too close or too far apart (with respect to the natural notion of distance); and is known to be a rigorous barrier for certain classes of algorithms. Establishing algorithmic hardness via the OGP consists essentially of two main steps: (a) establishing the OGP (which, often times, is done by the so-called first moment method); and (b) leveraging the OGP to rule out specific classes of algorithms (often by a contradiction argument).

In this talk, we focus on the technical details of the latter step while using the random number partitioning problem as a running example. Specifically, we will show (a) how to leverage the multi-OGP (m-OGP) to rule out stable algorithms, appropriately defined; and (b) how to leverage the ``vanilla” 2-OGP to establish the existence of Free Energy Wells (FEW) which implies slow mixing for a very natural Monte Carlo Markov Chain dynamics at sufficiently low temperatures. Interestingly, our proof of the failure of stable algorithms via m-OGP employs methods from Ramsey Theory from the extremal combinatorics and is of independent interest.

In this talk we will discuss a line of work that tries to define and analyze the Overlap Gap Property (OGP) in the context of estimation of a hidden structure. We will discuss some of the results and intuition (as well as some cool open problems) which arise from the study of OGP in the context of the conjectured “hard” regimes of sparse regression, planted clique and sparse PCA.

Abstract: We study support recovery for a hidden k \times k principal submatrix with elevated mean in a symmetric Gaussian N \times N matrix. Throughout we assume that we are in a proportional sparsity regime, i.e. $k = N \rho$, $\rho \in (0,1)$. We will characterize the information theoretic threshold for non-trivial support recovery, and provide some evidence for a hard phase via OGP. As a consequence, we will rule out a natural family of MCMC algorithms.

I'll mainly focus on the use of variational methods (based on the Parisi formula) to establish OGP. I'll also connect our results with subsequent work, and highlight some open questions.

Based on joint work with David Gamarnik (MIT) and Aukosh Jagannath (UWaterloo).

We study the problem of algorithmically optimizing the Hamiltonian H_N of a spherical or Ising mixed p-spin glass. The maximum asymptotic value OPT of H_N/N is characterized by a variational principle known as the Parisi formula, proved first by Talagrand and in more generality by Panchenko. Recently developed approximate message passing algorithms efficiently optimize H_N/N up to a value ALG given by an extended Parisi formula, which minimizes over a larger space of functional order parameters. These two objectives are equal for spin glasses exhibiting a no overlap gap property. However, ALG < OPT can also occur, and no efficient algorithm producing an objective value exceeding ALG is known.

We prove that for mixed even p-spin models, no algorithm satisfying an overlap concentration property can produce an objective larger than ALG with non-negligible probability. This property holds for all algorithms with suitably Lipschitz dependence on the disorder coefficients of H_N. It encompasses natural formulations of gradient descent, approximate message passing, and Langevin dynamics run for bounded time and in particular includes the algorithms achieving ALG mentioned above. To prove this result, we substantially generalize the overlap gap property framework introduced by Gamarnik and Sudan to arbitrary ultrametric forbidden structures of solutions.

QAOA is a quantum algorithm which holds a lot of promise since it can be implemented, and in fact was implemented in current quantum computers, with low overhead. It is designed to solve combinatorial optimization problems with local cost structure. We will discuss the limits of QAOA when run on random graphs. We will show that the algorithm cannot solve the largest independent set problem in a sparse random graph up to a multiplicative constant, if the number of layers of the QAOA (which I will define) is at most logarithmic in the problem size with a small multiplier. Namely the algorithm needs to "see the entire graph" so to speak.

The proof is based on the presence of the Overlap Gap Property for the independent set problem coupled with the long range independence exhibited by the QAOA output at logarithmic depth.

Joint work with Edward Farhi and Sam Gutmann.