Overlap Gap Property: A topological barrier to optimization in random structures

par David Gamarnik

jeudi 20 nov. 2025, 14:00 → 15:00 Europe/Paris

435 (ENS)

Many optimization problem involving randomness exhibit a gap between optimal values on the one hand, and the best values achievable by known fast (polynomial time) algorithms. Two illustrative examples to be discussed in the talk are ground states of a spin glasses and largest submatrix of a random matrix.  At the same time, the formal hardness of these problems in the form of the complexity-theoretic NP-hardness is lacking. 

We introduce a new approach for understanding algorithmic intractability of such optimization problems, which is based on the topological disconnectivity of the space of near optimal solutions, called the Overlap Gap Property (OGP). The property traces back to the Parisi's  replica symmetry breaking method, and the subsequent mathematically rigorous validation of it by Talagrand. We will prove that OGP is indeed a barrier to bridging such algorithmic gaps for large classes of algorithms, specifically stable (noise-insensitive) and online algorithms. It is notable that these are precisely the algorithms which achieve the best currently known values. Ground states of spin glasses and the largest submatrix problem will serve as illustration for these ideas.