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
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 564
Quantum optimization of maximum independent set using Rydberg atom arrays
Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., et al. (2022) · Science · doi:10.1126/science.abo6587 · Cited by 430
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
Basso, J., Farhi, E., Marwaha, K., Villalonga, B., & Zhou, L. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.tqc.2022.7 · Cited by 116
NLTS Hamiltonians from Good Quantum Codes
Anshu, A., Breuckmann, N. P., & Nirkhe, C. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585114 · Cited by 73
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
