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
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Analytic and Algorithmic Solution of Random Satisfiability Problems
Mézard, M., Giorgio Parisi, A., & Zecchina, R. (2002) · Science · doi:10.1126/science.1073287 · Cited by 1,045
A sequence of approximated solutions to the S-K model for spin glasses
Giorgio Parisi, A. (1980) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/13/4/009 · Cited by 858
Determining computational complexity from characteristic ‘phase transitions’
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999) · Nature · doi:10.1038/22055 · Cited by 781
The Loss Surfaces of Multilayer Networks
Choromanska, A., Henaff, M., Mathieu, M., Arous, G. B., & LeCun, Y. (2014) · arXiv · doi:10.48550/arxiv.1412.0233 · Cited by 733
Sharp thresholds of graph properties, and the $k$-sat problem
Friedgut, E., & Bourgain, A. B. J. (1999) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-99-00305-7 · Cited by 677
Generating Hard Instances of Lattice ProblemsPreprint
Ajtai, M. (1996) · Electronic colloquium on computational complexity · Cited by 606
Critical Behavior in the Satisfiability of Random Boolean Expressions
Kirkpatrick, S., & Selman, B. (1994) · Science · doi:10.1126/science.264.5163.1297 · Cited by 582
Gibbs states and the set of solutions of random constraint satisfaction problems
Krząkała, F., Andrea Montanari, A., Ricci‐Tersenghi, F., Semerjian, G., & Zdeborová, L. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0703685104 · Cited by 546
Algorithms and Complexity: New Directions and Recent Results
Traub, J. F. (1976) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 427
The Sherrington-Kirkpatrick Model
Panchenko, D. (2013) · Springer monographs in mathematics · doi:10.1007/978-1-4614-6289-7 · Cited by 381
Large Cliques Elude the Metropolis Process
Jerrum, M. (1992) · Random Structures and Algorithms · doi:10.1002/rsa.3240030402 · Cited by 332
Application of statistical mechanics to NP-complete problems in combinatorial optimisation
Fu, Y., & Anderson, P. W. (1986) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/19/9/033 · Cited by 330
Storage capacity of memory networks with binary couplings
Krauth, W., & Mézard, M. (1989) · Journal de physique · doi:10.1051/jphys:0198900500200305700 · Cited by 279
Lipton, R. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002/13 · Cited by 270
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical CasePreprint
Farhi, E., Gamarnik, D., & Gutmann, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2004.09002 · Cited by 209
Self-citationClustering of Solutions in the Random Satisfiability Problem
Mézard, M., Mora, T., & Zecchina, R. (2005) · Physical Review Letters · doi:10.1103/physrevlett.94.197205 · Cited by 208
The Differencing Method of Set Partitioning
Karmarker, N., & Karp, R. M. (1983) · Cited by 207
On the solution-space geometry of random constraint satisfaction problems
Achlioptas, D., & Ricci‐Tersenghi, F. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132537 · Cited by 155
Learning by Message Passing in Networks of Discrete Synapses
Braunstein, A., & Zecchina, R. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.030201 · Cited by 149
Optimization of the Sherrington-Kirkpatrick Hamiltonian
Andrea Montanari, A. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00087 · Cited by 138
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems
Hopkins, S. B., & Steurer, D. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.42 · Cited by 136
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case ExamplesPreprint
Farhi, E., Gamarnik, D., & Gutmann, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.08747 · Cited by 134
Self-citationThe Power of Sum-of-Squares for Detecting Hidden Structures
Hopkins, S. B., Kothari, P. K., Potechin, A. H., Raghavendra, P., Schramm, T., & Steurer, D. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.72 · Cited by 116
Proof of the Satisfiability Conjecture for Large k
Ding, J., Sly, A., & Sun, N. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746619 · Cited by 110
Disorder chaos and multiple valleys in spin glassesPreprint
Chatterjee, S. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0907.3381 · Cited by 91
A Better Algorithm for Random k -SAT
Coja‐Oghlan, A. (2010) · SIAM Journal on Computing · doi:10.1137/09076516x · Cited by 89
Local algorithms for independent sets are half-optimal
Rahman, M., & Virág, B. (2017) · The Annals of Probability · doi:10.1214/16-aop1094 · Cited by 88
Proof of the satisfiability conjecture for large $k$
Ding, J., Sly, A., & Sun, N. (2022) · Annals of Mathematics · doi:10.4007/annals.2022.196.1.1 · Cited by 88
Communication is Bounded by Root of Rank
Lovett, S. (2016) · Journal of the ACM · doi:10.1145/2724704 · Cited by 87
Ricci‐Tersenghi, F., & Semerjian, G. (2009) · HAL · Cited by 79
Optimization of mean-field spin glasses
Alaoui, A. E., Andrea Montanari, A., & Sellke, M. (2021) · The Annals of Probability · doi:10.1214/21-aop1519 · Cited by 73
Limits of local algorithms over sparse random graphs
Gamarnik, D., & Sudan, M. (2017) · The Annals of Probability · doi:10.1214/16-aop1114 · Cited by 73
Self-citationRicci‐Tersenghi, F., & Semerjian, G. (2009) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2009/09/p09001 · Cited by 71
The backtracking survey propagation algorithm for solving random K-SAT problems
Marino, R., Giorgio Parisi, A., & Ricci‐Tersenghi, F. (2016) · Nature Communications · doi:10.1038/ncomms12996 · Cited by 62
Low-Degree Hardness of Random Optimization Problems
Gamarnik, D., Jagannath, A., & Wein, A. S. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00021 · Cited by 56
Self-citationThe landscape of the planted clique problem: Dense subgraphs and the overlap gap property
Gamarnik, D., & Zadik, I. (2024) · The Annals of Applied Probability · doi:10.1214/23-aap2003 · Cited by 55
Self-citationSuboptimality of local algorithms for a class of max-cut problems
Chen, W., Gamarnik, D., Panchenko, D., & Rahman, M. (2019) · The Annals of Probability · doi:10.1214/18-aop1291 · Cited by 54
Self-citationProof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
Abbe, E. A., Li, S., & Sly, A. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00041 · Cited by 52
Optimal low-degree hardness of maximum independent set
Wein, A. S. (2022) · Mathematical Statistics and Learning · doi:10.4171/msl/25 · Cited by 50
Frozen 1-RSB structure of the symmetric Ising perceptron
Perkins, W., & Xu, C. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451119 · Cited by 49
Following the Ground States of Full‐RSB Spherical Spin Glasses
Subag, E. (2020) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21922 · Cited by 45
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
Bresler, G., & Huang, B. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00038 · Cited by 44
The overlap gap property and approximate message passing algorithms for $p$-spin models
Gamarnik, D., & Jagannath, A. (2021) · The Annals of Probability · doi:10.1214/20-aop1448 · Cited by 41
Self-citationCapacity lower bound for the Ising perceptron
Ding, J., & Sun, N. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316383 · Cited by 41
Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
Gamarnik, D., & Sudan, M. (2017) · SIAM Journal on Computing · doi:10.1137/140989728 · Cited by 40
Self-citationAnalysis of the Karmarkar-Karp differencing algorithm
Boettcher, S., & Mertens, S. (2008) · The European Physical Journal B · doi:10.1140/epjb/e2008-00320-9 · Cited by 40
Analysis of the Karmarkar-Karp Differencing AlgorithmPreprint
Boettcher, S., & Mertens, S. (2008) · Cited by 36
On the energy landscape of the mixed even p-spin model
Chen, W.-K., Handschy, M., & Lerman, G. (2017) · Probability Theory and Related Fields · doi:10.1007/s00440-017-0773-1 · Cited by 34
Walksat Stalls Well Below Satisfiability
Coja-Oghlan, A., Haqshenas, A., & Hetterich, S. (2017) · SIAM Journal on Discrete Mathematics · doi:10.1137/16m1084158 · Cited by 33
Covering Cubes by Random Half Cubes, with Applications to Binary Neural Networks
Kim, J. H., & Roche, J. R. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1560 · Cited by 32
Finding a large submatrix of a Gaussian random matrix
Gamarnik, D., & Li, Q. (2018) · The Annals of Statistics · doi:10.1214/17-aos1628 · Cited by 32
Self-citationBeing Glassy Without Being Hard to Solve
Ricci‐Tersenghi, F. (2010) · Science · doi:10.1126/science.1189804 · Cited by 32
Gamarnik, D., & Zadik, I. (2017) · Conference on Learning Theory · Cited by 31
Self-citationAlgorithmic obstructions in the random number partitioning problem
Gamarnik, D., & Kızıldağ, E. C. (2023) · The Annals of Applied Probability · doi:10.1214/23-aap1953 · Cited by 30
Self-citationThe overlap gap property in principal submatrix recovery
Gamarnik, D., Jagannath, A., & Sen, S. (2021) · Probability Theory and Related Fields · doi:10.1007/s00440-021-01089-7 · Cited by 27
Self-citationEntropic barriers as a reason for hardness in both classical and quantum algorithms
Bellitti, M., Ricci‐Tersenghi, F., & Scardicchio, A. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.043015 · Cited by 25
On belief propagation guided decimation for random k-SAT
Coja‐Oghlan, A. (2011) · doi:10.5555/2133036.2133110 · Cited by 25
Biased landscapes for random constraint satisfaction problems
Budzynski, L., Ricci‐Tersenghi, F., & Semerjian, G. (2019) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ab02de · Cited by 23
Clustering of solutions in the symmetric binary perceptron
Baldassi, C., Vecchia, R. D., Lucibello, C., & Zecchina, R. (2020) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ab99be · Cited by 22
Analysing Survey Propagation Guided Decimation on Random FormulasPreprint
Hetterich, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.08519 · Cited by 21
Following the ground-states of full-RSB spherical spin glassesPreprint
Subag, E. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.04588 · Cited by 20
A Better Algorithm for Random k-SAT
Coja‐Oghlan, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02927-1_25 · Cited by 19
Free Energy Wells and Overlap Gap Property in Sparse PCA
Arous, G. B., Wein, A. S., & Zadik, I. (2022) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.22083 · Cited by 18
Gomes, C. P., & Selman, B. (2002) · Science · doi:10.1126/science.1074599 · Cited by 18
Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average
Gamarnik, D., & Kızıldağ, E. C. (2020) · The Annals of Applied Probability · doi:10.1109/isit44484.2020.9174373 · Cited by 16
Self-citationA Simple Approach to Chaos For p-Spin Models
Eldan, R. (2020) · Journal of Statistical Physics · doi:10.1007/s10955-020-02626-9 · Cited by 15
Shattering versus metastability in spin glasses
Arous, G. B., & Jagannath, A. (2023) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.22133 · Cited by 14
Belief Propagation Guided Decimation Fails on Random Formulas
Coja‐Oghlan, A. (2017) · Journal of the ACM · doi:10.1145/3005398 · Cited by 14
Balancing Gaussian vectors in high dimensionPreprint
Turner, P., Meka, R., & Rigollet, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.13972 · Cited by 11
Balancing covariates in randomized experiments using the Gram-Schmidt walk.Preprint
Harshaw, C., Sävje, F., Spielman, D. A., & Zhang, P. (2019) · arXiv (Cornell University) · Cited by 10
Approximate Ground States of Hypercube Spin Glasses are Near Corners
Sellke, M. (2021) · Comptes Rendus Mathématique · doi:10.5802/crmath.240 · Cited by 7
Analysing Survey Propagation Guided Decimationon Random Formulas
Hetterich, S. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2016.65 · Cited by 7
Budzynski, L., & Semerjian, G. (2020) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/abb8c8 · Cited by 6
The Sherrington-Kirkpatrick Model
Talagrand, M. (2010) · Springer eBooks · doi:10.1007/978-3-642-15202-3_1 · Cited by 5
Large independent sets on random d-regular graphs with d smallPreprint
Marino, R., & Kirkpatrick, S. (2020) · arXiv (Cornell University) · doi:10.13140/rg.2.2.14714.44489 · Cited by 1
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
