2026-08-10T23:54:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24414 2025-12-12T15:01:38Z ddc:004 open_access

Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT Kızıldağ, Eren C. spin glasses p-spin model random constraint satisfaction problems overlap gap property phase transitions computational complexity 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 Frieze [Frieze, 1990] and exploiting concentration properties of carefully constructed random variables. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eren C. Kızıldağ 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.48 urn:nbn:de:0030-drops-244147 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.48 eng https://creativecommons.org/licenses/by/4.0/legalcode