Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT

Abstract

The Ising $p$-spin glass and random $k$-SAT are two canonical examples of disordered systems that play a central role in understanding the link between geometric features of optimization landscapes and computational tractability. Both models exhibit hard regimes where all known polynomial-time algorithms fail and possess the multi Overlap Gap Property ($m$-OGP), an intricate geometrical property that rigorously rules out a broad class of algorithms exhibiting input stability. We establish that, in both models, the symmetric $m$-OGP undergoes a sharp phase transition, and we pinpoint its exact threshold. For the Ising $p$-spin glass, our results hold for all sufficiently large $p$; for the random $k$-SAT, they apply to all $k$ growing mildly with the number of Boolean variables. Notably, our findings yield qualitative insights into the power of OGP-based arguments. A particular consequence for the Ising $p$-spin glass is that the strength of the $m$-OGP in establishing algorithmic hardness grows without bound as $m$ increases. These are the first sharp threshold results for the $m$-OGP. Our analysis hinges on a judicious application of the second moment method, enhanced by concentration. While a direct second moment calculation fails, we overcome this via a refined approach that leverages an argument of~\cite{frieze1990independence} and exploiting concentration properties of carefully constructed random variables.

APPROX/RANDOM 2025