Sharp Phase Transitions for the Overlap Gap Property

Abstract.

The Ising [Formula: see text]-spin glass and random [Formula: see text]-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 ([Formula: see text]-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 [Formula: see text]-OGP undergoes a sharp phase transition, and we pinpoint its exact threshold. For the Ising [Formula: see text]-spin glass, our results hold for all sufficiently large [Formula: see text]; for the random [Formula: see text]-SAT, they apply to all [Formula: see text] 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 [Formula: see text]-spin glass is that the strength of the [Formula: see text]-OGP in establishing algorithmic hardness is strictly monotone in [Formula: see text]. These are the first sharp threshold results for the [Formula: see text]-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 [A. M. Frieze,  Discrete Math., 81 (1990), pp. 171–175] and exploits concentration properties of carefully constructed random variables.