Sharp Phase Transitions for the Overlap Gap Property
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1266-1303
DOI: 10.1137/25m1790531 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 20.08.2026. Verfasst von Eren C. Kızıldağ. Die Arbeit nennt 106 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Kızıldağ, E. C. (2026). Sharp Phase Transitions for the Overlap Gap Property. SIAM Journal on Discrete Mathematics, 40(3), 1266-1303. https://doi.org/10.1137/25m1790531
Vancouver
Kızıldağ EC. Sharp Phase Transitions for the Overlap Gap Property. SIAM Journal on Discrete Mathematics. 2026;40(3):1266-1303. doi:10.1137/25m1790531
BibTeX
@article{Kzlda2026,
author = {Kızıldağ, Eren C.},
title = {Sharp Phase Transitions for the Overlap Gap Property},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {1266--1303},
doi = {10.1137/25m1790531}
}
EUVIMED