The DOI matches its Crossref record; 86 of the 92 references it cites were found in a registry or an index.
The overlap gap property: A topological barrier to optimizing over random structures
Open accessAbstract
The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures, finding optimal solutions by means of fast algorithms is not known and often is believed not to be possible. At the same time, the formal hardness of these problems in the form of the complexity-theoretic NP -hardness is lacking. A new approach for algorithmic intractability in random structures is described in this article, which is based on the topological disconnectivity property of the set of pairwise distances of near-optimal solutions, called the Overlap Gap Property. The article demonstrates how this property 1) emerges in most models known to exhibit an apparent algorithmic hardness; 2) is consistent with the hardness/tractability phase transition for many models analyzed to the day; and, importantly, 3) allows to mathematically rigorously rule out a large class of algorithms as potential contenders, specifically the algorithms that exhibit the input stability (insensitivity).
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“They showed analytically that, due to this property, the QAOA needs increasingly high p -values for Maxk XOR with even k .”
From Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems (2024) · cites this paper as [25]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Solvable Model of a Spin-Glass
Sherrington, D., & Kirkpatrick, S. (1975) · Physical Review Letters · doi:10.1103/physrevlett.35.1792 · Cited by 4,349
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications
Mezard, M., Parisi, G., & Virasoro, M. (1986) · World Scientific Lecture Notes in Physics · doi:10.1142/0271 · Cited by 3,653
Mézard, M., Giorgio Parisi, A., VIRASORO, M. A., & Thouless, D. J. (1988) · Physics Today · doi:10.1063/1.2811676 · Cited by 2,683
A Mathematical Introduction to Compressive Sensing
Foucart, S., & Rauhut, H. (2013) · Applied and numerical harmonic analysis · doi:10.1007/978-0-8176-4948-7 · Cited by 2,662
Vershynin, R. (2018) · Cambridge University Press eBooks · doi:10.1017/9781108231596 · Cited by 2,649
Statistics for High-Dimensional Data
Bühlmann, P., & van de Geer, S. (2011) · Springer series in statistics · doi:10.1007/978-3-642-20192-9 · Cited by 2,647
Information, Physics, and Computation
Mézard, M., & Andrea Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,998
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Generating hard instances of lattice problems (extended abstract)
Ajtai, M. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.237838 · Cited by 1,434
Research works printed but not linked: 3
- M. R. Garey, D.S. Johnson, Computers and Intractability (Series of Books in the Mathematical Sciences, Freeman, San Francisco, CA, 1979), vol. 174.
- S. Hopkins “Statistical inference and the sum of squares method ” PhD thesis Cornell University Ithaca NY (2018).
- M. Talagrand, Basic Examples (Mean Field Models for Spin Glasses, Springer, Berlin, Germany, 2010), vol. 1.
Cited by
Items 101–135 of 135
Binary perceptron computational gap: a parametric fl-RDT view
Stojnic, M. (2026) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ae4f7f · Cited by 1
Universal energy-space localization and stable quantum phases against time-dependent perturbations
Yu, H., & Wei, T.-C. (2026) · Nature Communications · doi:10.1038/s41467-026-75465-z · Cited by 1
Closest-vector problem and the zero-temperature p -spin landscape for lossy compression
Braunstein, A., Budzynski, L., Crotti, S., & Ricci‐Tersenghi, F. (2022) · Physical review. E · doi:10.1103/physreve.106.054101 · Cited by 1
Benchmarking the optimization of optical machines with the planted solutions
Stroev, N., Berloff, N. G., & Davidson, N. (2024) · Communications Physics · doi:10.1038/s42005-024-01870-9 · Cited by 1
Belief Propagation Guided Decimation on Random k-XORSAT
Chatterjee, A., Coja‐Oghlan, A., Kang, M., Krieg, L., Rolvien, M., & Sorkin, G. B. (2025) · London School of Economics and Political Science Research Online (London School of Economics and Political Science) · doi:10.4230/lipics.icalp.2025.47 · Cited by 1
Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
Boettcher, S., & Lau, G. E. (2025) · Physical Review Letters · doi:10.1103/j159-lpfx · Cited by 1
Li, Z. (2026) · IEEE Transactions on Information Theory · doi:10.1109/tit.2026.3659093 · Cited by 1
Generative diffusion for perceptron problems: statistical physics analysis and efficient algorithms
Straziota, D., Demyanenko, E., Baldassi, C., & Lucibello, C. (2025) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ae8ceb · Cited by 1
The Stochastic Model for Queue Simulation
Sianturi, R. (2025) · Bulletin of Pedagogical Research · doi:10.51278/bpr.v5i1.1747 · Cited by 1
On the evidence for a statistical-computational gap raised by the Group Testing Problem
Gebhard, O. (2022) · Publication Server of Goethe University Frankfurt am Main (Goethe University Frankfurt) · doi:10.21248/gups.68926 · Cited by 1
Nonlocal Monte Carlo via Reinforcement LearningPreprint
Dobrynin, D., Mohseni, M., & Strachan, J. P. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2508.10520 · Cited by 1
Grimaldi, A., Duffee, C., Raimondo, E., Piccolo, E., Volpe, D., Maciejewski, F. B., Carpentieri, M., Chiappini, M., Amiri, P. K., Venturelli, D., et al. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2605.07884 · Cited by 1
Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted CliquePreprint
Bresler, G., & Jiang, T. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2306.17719
Limits of Sequential Local Algorithms on the Random $k$-XORSAT ProblemPreprint
Yung, K. (2024) · arXiv (Cornell University) · doi:10.4230/lipics.icalp.2024.123
A Random CSP with Connections to Discrepancy Theory and Randomized Trials
Kızıldağ, E. C. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619571
Istrate, G. (2024) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.410.3
Learning by Steering the Neural Dynamics: A Statistical Mechanics PerspectivePreprint
Scardecchia, M. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2510.11984
Gap Amplification for Reconfiguration Problems
Ohsaka, N. (2025) · ACM Transactions on Algorithms · doi:10.1145/3779053
Jankola, M., Behrens, F., Koller, C., & Zdeborová, L. (2026) · Physical review. E · doi:10.1103/b8vm-fz49
Canfora, F., & Cedeño, M. V. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2601.18968
(2025) · SciPost Physics · doi:10.21468/scipost.report.12461
New perspectives and tools for Tensor Principal Component Analysis and beyond
Ouerfelli, M. (2022) · theses.fr (ABES) · doi:10.70675/0438984az76b6z487bz87b1z6da865daa43e
Algorithmic aspects of the continuous random energy model
Ho, F.-H. (2023) · theses.fr (ABES) · doi:10.70675/c166369az6b57z4754za3aaz5b238671cddd
Nayyeri, A., Taheri, M., & Mansoori, E. G. (2026) · IEEE Access · doi:10.1109/access.2026.3685978
Zhang, Z. (2026) · Scientia Sinica Mathematica · doi:10.1360/ssm-2026-0032
The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut ProblemPreprint
Mints, M., & Anschuetz, E. R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.10838
The overlap gap property and its implication for the quantum approximate optimisation algorithm
Goh, M. X. H. (2026) · Kölner Universitäts PublikationsServer (Universität zu Köln)
On the robustness of noisy solutions in non-convex neural networks
Malatesta, E. M., Passalacqua, A., & Zecchina, R. (2026) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/aeafec
Sharp Phase Transitions for the Overlap Gap Property
Kızıldağ, E. C. (2026) · SIAM Journal on Discrete Mathematics · doi:10.1137/25m1790531
Ground-State Energy of Multipartite $p$-Spin GlassesPreprint
Sahin, B. A., & Kızıldağ, E. C. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.7356176
Dai, Q., & Shao, Z. (2026) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2026.3734096
Goh, M., & Müller, T. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.35131
Statistical Physics Methods for Non-Convex Neural Network Models
Annesi, B. L. (n.d.) · Archivio istituzionale della Ricerca - Bocconi
Navigating Rough Landscapes: Statistical Physics Approaches to Machine Learning and Inference
Straziota, D. (n.d.) · Archivio istituzionale della Ricerca - Bocconi
Lee-Yang theorems for $q$-deformed oscillators and doubly-scaled SYKPreprint
Basu, A., & Midha, S. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2611.03624
Metadata
- Authors
- Gamarnik, D.
- Affiliations
- Massachusetts Institute of Technology (US)
- Corresponding author
- Gamarnik, David
- ORCID
- Gamarnik, David
- Venue
- Proceedings of the National Academy of Sciences
- Publisher
- National Academy of Sciences
- Published
- 2021-10
- Volume
- 118
- Issue
- 41
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- PMC
- PMC8521669
- OpenAlex
- W3202733572
- Cited by
- 103
- References
- 92
- Citations by year
- 2026: 20 · 2025: 32 · 2024: 22 · 2023: 12 · 2022: 15 · 2021: 2
- FWCI
- 5.72
- Type
- journal article
- Language
- en
- Open access
- green
- www.ncbi.nlm.nih.gov
- Locations
- Proceedings of the National Academy of Sciences (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Constraint Satisfaction and Optimization
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Physics and Astronomy › Condensed Matter Physics › Theoretical and Computational Physics
- Keywords
- overlap gap property, NP-hardness, statistical physics models
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
