EUVIMEDEUVIMED entdecken
Crossref

Sharp Phase Transitions for the Overlap Gap Property

Eren C. Kızıldağ

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →