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
Quantum-Informed Recursive Optimization Algorithms
Finžgar, J. R., Kerschbaumer, A., Schuetz, M. J. A., Mendl, C. B., & Katzgraber, H. G. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020327 · Cited by 63
Basso, J., Gamarnik, D., Mei, S., & Zhou, L. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00039 · Cited by 47
Self-citationDisordered systems insights on computational hardness
Gamarnik, D., Moore, C., & Zdeborová, L. (2022) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ac9cc8 · Cited by 46
Self-citationThe 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
Tight Lipschitz hardness for optimizing mean field spin glasses
Huang, B., & Sellke, M. (2024) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.22222 · Cited by 44
Liu, J.-G., Gao, X., Cain, M., Lukin, M. D., & Wang, S.-T. (2023) · SIAM Journal on Scientific Computing · doi:10.1137/22m1501787 · Cited by 43
Algorithms and Barriers in the Symmetric Binary Perceptron Model
Gamarnik, D., Kızıldağ, E. C., Perkins, W., & Xu, C. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00061 · Cited by 42
Self-citationOn the free energy of vector spin glasses with nonconvex interactions
Chen, H., & Mourrat, J.-C. (2025) · Probability and Mathematical Physics · doi:10.2140/pmp.2025.6.1 · Cited by 35
NLTS Hamiltonians from Good Quantum Codes
Anshu, A., Breuckmann, N. P., & Nirkhe, C. (2026) · SIAM Journal on Computing · doi:10.1137/23m1608045 · Cited by 35
Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses
Huang, B., & Sellke, M. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00037 · Cited by 33
Angelini, M. C., & Ricci‐Tersenghi, F. (2023) · Physical Review X · doi:10.1103/physrevx.13.021011 · Cited by 32
Evolving scientific discovery by unifying data and background knowledge with AI Hilbert
Cory-Wright, R., Cornelio, C., Dash, S., Khadir, B. E., & Lior Horesh, C. (2024) · Nature Communications · doi:10.1038/s41467-024-50074-w · Cited by 32
Solving Nonnative Combinatorial Optimization Problems Using Hybrid Quantum–Classical Algorithms
Wurtz, J., Sack, S. H., & Wang, S.-T. (2024) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2024.3443660 · Cited by 32
Gamarnik, D., Jagannath, A., & Wein, A. S. (2024) · SIAM Journal on Computing · doi:10.1137/22m150263x · 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-citationShattering in the Ising p-spin glass model
Gamarnik, D., Jagannath, A., & Kızıldağ, E. C. (2025) · Probability Theory and Related Fields · doi:10.1007/s00440-025-01414-4 · Cited by 30
Self-citationEnergy landscapes of combinatorial optimization in Ising machines
Dobrynin, D., Renaudineau, A., Hizzani, M., Strukov, D. B., Mohseni, M., & Strachan, J. P. (2024) · Physical review. E · doi:10.1103/physreve.110.045308 · Cited by 29
Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End
Dalzell, A. M., Pancotti, N., Campbell, E. T., & Brandão, F. G. S. L. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585203 · Cited by 27
Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
Anshu, A., & Metger, T. (2023) · Quantum · doi:10.22331/q-2023-05-11-999 · Cited by 26
Typical and atypical solutions in nonconvex neural networks with discrete and continuous weights
Baldassi, C., Malatesta, E. M., Perugini, G., & Zecchina, R. (2023) · Physical review. E · doi:10.1103/physreve.108.024310 · Cited by 26
Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPsPreprint
Chen, A., Huang, N., & Marwaha, K. (2023) · arXiv (Cornell University) · doi:10.4230/lipics.approx/random.2026.78 · Cited by 26
Strongly Interacting Fermions Are Nontrivial yet Nonglassy
Anschuetz, E. R., Chen, C.-F., Kiani, B. T., & King, R. (2025) · Physical Review Letters · doi:10.1103/cbqf-d24r · Cited by 25
Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm
Boulebnane, S., Khan, A., Liu, M., Larson, J. M., Herman, D., Shaydulin, R., & Pistoia, M. (2026) · Physical Review Letters · doi:10.1103/2w94-rymn · Cited by 21
Single-layer digitized-counterdiabatic quantum optimization for p-spin models
Guan, H., Zhou, F., Albarrán-Arriagada, F., Chen, X., Solano, E., Hegade, N. N., & Huang, H.-L. (2024) · Quantum Science and Technology · doi:10.1088/2058-9565/ad7880 · Cited by 19
Bounds on the Ground State Energy of Quantum p-Spin Hamiltonians
Anschuetz, E. R., Gamarnik, D., & Kiani, B. T. (2025) · Communications in Mathematical Physics · doi:10.1007/s00220-025-05412-4 · Cited by 17
Self-citationMissing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
Wybo, E., & Leib, M. (2025) · Quantum · doi:10.22331/q-2025-10-22-1892 · Cited by 16
A Polynomial Time Iterative Algorithm for Matching Gaussian Matrices with Non-vanishing Correlation
Ding, J., & Li, Z. (2024) · Foundations of Computational Mathematics · doi:10.1007/s10208-024-09662-x · Cited by 16
Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
Annesi, B. L., Malatesta, E. M., & Zamponi, F. (2025) · SciPost Physics · doi:10.21468/scipostphys.18.4.118 · Cited by 14
Hardness of Sampling Solutions From the Symmetric Binary Perceptron
Alaoui, A. E., & Gamarnik, D. (2025) · Random Structures and Algorithms · doi:10.1002/rsa.70021 · Cited by 14
Self-citationThe threshold energy of low temperature Langevin dynamics for pure spherical spin glasses
Sellke, M. (2024) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.22197 · Cited by 14
Barriers for the performance of graph neural networks (GNN) in discrete random structures
Gamarnik, D. (2023) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2314092120 · Cited by 13
Self-citationA short review on the maximum clique problem algorithms with classical, AI, and quantum methods
Marino, R., Buffoni, L., & Zaválnij, B. (2026) · Communications Physics · doi:10.1038/s42005-026-02606-7 · Cited by 13
Combinatorial NLTS From the Overlap Gap Property
Anschuetz, E. R., Gamarnik, D., & Kiani, B. T. (2024) · Quantum · doi:10.22331/q-2024-11-19-1527 · Cited by 13
Self-citationSharp Phase Transitions in Estimation with Low-Degree Polynomials
Sohn, Y., & Wein, A. S. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718294 · Cited by 13
Alaoui, A. E. (2025) · Stochastic Processes and their Applications · doi:10.1016/j.spa.2025.104792 · Cited by 13
Chen, G., Ding, J., Gong, S., & Li, Z. (2026) · The Annals of Statistics · doi:10.1214/25-aos2565 · Cited by 13
Sampling diverse near-optimal solutions via algorithmic quantum annealing
Mohseni, M., Rams, M. M., Isakov, S. V., Eppens, D., Pielawa, S., Strümpfer, J., Boixo, S., & Neven, H. (2023) · Physical review. E · doi:10.1103/physreve.108.065303 · Cited by 13
Hard optimization problems have soft edges
Marino, R., & Kirkpatrick, S. (2023) · Scientific Reports · doi:10.1038/s41598-023-30391-8 · Cited by 13
Symmetric Perceptrons, Number Partitioning and Lattices
Vafa, N., & Vaikuntanathan, V. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718263 · Cited by 12
The algorithmic phase transition of random graph alignment problem
Du, H., Gong, S., & Huang, R. (2025) · Probability Theory and Related Fields · doi:10.1007/s00440-025-01370-z · Cited by 12
High-dimensional manifold of solutions in neural networks: insights from statistical physicsPreprint
Malatesta, E. M. (2023) · arXiv (Cornell University) · doi:10.48550/arxiv.2309.09240 · Cited by 12
Barbier, D. (2025) · SciPost Physics · doi:10.21468/scipostphys.18.3.115 · Cited by 11
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
Wein, A. S. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585232 · Cited by 11
Searching for (sharp) thresholds in random structures: Where are we now?
Perkins, W. (2024) · Bulletin of the American Mathematical Society · doi:10.1090/bull/1857 · Cited by 10
Quantum Glassiness from Efficient Learning
Anschuetz, E. R. (2026) · Communications in Mathematical Physics · doi:10.1007/s00220-025-05536-7 · Cited by 9
(Dis)assortative partitions on random regular graphs
Behrens, F., Arpino, G., Kivva, Y., & Zdeborová, L. (2022) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ac8b46 · Cited by 9
Gap Amplification for Reconfiguration Problems
Ohsaka, N. (2024) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977912.54 · Cited by 9
Algorithmic Thresholds in Combinatorial Optimization Depend on the Time Scaling
Angelini, M. C., Avila-González, M., D’Amico, F., Machado, D., Mulet, R., & Ricci‐Tersenghi, F. (2025) · Physical Review X · doi:10.1103/dw9m-95vv · Cited by 9
Friendly bisections of random graphs
Ferber, A., Kwan, M., Narayanan, B. P., Sah, A., & Sawhney, M. S. (2022) · Communications of the American Mathematical Society · doi:10.1090/cams/13 · Cited by 9
Statistical mechanics of the maximum-average submatrix problem
Erba, V., Krząkała, F., Ortiz, R. P., & Zdeborová, L. (2024) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ad1391 · Cited by 8
Generating hard Ising instances with planted solutions using post-quantum cryptographic protocols
Mandrà, S., Munoz-Bauza, H., Mossi, G., & Rieffel, E. G. (2025) · Future Generation Computer Systems · doi:10.1016/j.future.2025.107721 · Cited by 8
Finding Planted Cliques Using Gradient Descent
Gheissari, R., Jagannath, A., & Xu, Y. (2025) · SIAM Journal on Mathematics of Data Science · doi:10.1137/24m1680489 · Cited by 8
Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
Bhamidi, S., Gamarnik, D., & Gong, S. (2026) · Electronic Communications in Probability · doi:10.1214/26-ecp759 · Cited by 7
Self-citationThe Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
Dhawan, A., & Wang, Y. (2026) · SIAM Journal on Discrete Mathematics · doi:10.1137/24m1701575 · Cited by 7
Damien, B. (2026) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ae8990 · Cited by 7
On the topology of solutions to random continuous constraint satisfaction problems
Kent-Dobias, J. (2025) · SciPost Physics · doi:10.21468/scipostphys.18.5.158 · Cited by 7
Un-inverting the Parisi formula
Mourrat, J.-C. (2025) · Annales de l Institut Henri Poincaré Probabilités et Statistiques · doi:10.1214/24-aihp1487 · Cited by 6
Counting and hardness-of-finding fixed points in cellular automata on random graphs
Koller, C., Behrens, F., & Zdeborová, L. (2024) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ad8797 · Cited by 6
Counting Random 𝑘-SAT near the Satisfiability Threshold
Chen, Z., Lonkar, A., Wang, C., Yang, K., & Yin, Y. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718163 · Cited by 6
The Overlap Gap Property Limits Limit Swapping in the QAOA
Goh, M. X. H. (2025) · Quantum Information and Computation · doi:10.2478/qic-2025-0018 · Cited by 6
Winstein, V. (2026) · The Annals of Applied Probability · doi:10.1214/26-aap2317 · Cited by 6
A polynomial‐time approximation scheme for the maximal overlap of two independent Erdős–Rényi graphs
Ding, J., Du, H., & Gong, S. (2024) · Random Structures and Algorithms · doi:10.1002/rsa.21212 · Cited by 6
On perfectly friendly bisections of random graphs
Minzer, D., Sah, A., & Sawhney, M. S. (2024) · The Annals of Probability · doi:10.1214/24-aop1696 · Cited by 6
Spin glasses and optimization in complex systems
Mézard, M. (2022) · Europhysics news · doi:10.1051/epn/2022105 · Cited by 6
Maximum Consensus by Weighted Influences of Monotone Boolean Functions
Zhang, E., Suter, D., Tennakoon, R., Chin, T.-J., Bab‐Hadiashar, A., Truong, G., & Gilani, S. Z. (2022) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52688.2022.00876 · Cited by 6
Müller, T., Singh, A., Wilhelm, F. K., & Bode, T. (2024) · arXiv · doi:10.48550/arxiv.2411.19388 · Cited by 5
Spin Glasses and the Parisi Formula
Mourrat, J.-C. (2026) · doi:10.1137/25m1804790 · Cited by 5
Densest Subgraphs of a Dense Erdös–Rényi Graph. Asymptotics, Landscape, and Universality
Cheairi, H. E., & Gamarnik, D. (2025) · SIAM Journal on Discrete Mathematics · doi:10.1137/24m1644924 · Cited by 5
Self-citationApproximate quadratization of high-order Hamiltonians for combinatorial quantum optimization
Drăgoi, S., Baiardi, A., & Egger, D. J. (2026) · Physical Review Research · doi:10.1103/9rc4-vj11 · Cited by 5
Local equations describe unreasonably efficient stochastic algorithms in random K-SAT
Machado, D., González-García, J., & Mulet, R. (2025) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2510153122 · Cited by 5
Partitioning problems via random processes
Anastos, M., Cooley, O., Kang, M., & Kwan, M. (2024) · Journal of the London Mathematical Society · doi:10.1112/jlms.70010 · Cited by 5
Overlap gap and computational thresholds in the square wave perceptron
Benedetti, M., Bogdanov, A., Malatesta, E. M., Mézard, M., Perrupato, G., Rosen, A., Schwartzbach, N. I., & Zecchina, R. (2025) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ae23be · Cited by 4
Dynamical learning in deep asymmetric recurrent neural networks
Badalotti, D., Baldassi, C., Mézard, M., Scardecchia, M., & Zecchina, R. (2026) · Physical Review Research · doi:10.1103/lbr6-91sn · Cited by 4
Compressed sensing with ℓ0-norm: statistical physics analysis & algorithms for signal recovery
Barbier, D., Lucibello, C., Saglietti, L., Krząkała, F., & Zdeborová, L. (2023) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw55543.2023.10161684 · Cited by 4
Low-Degree Method Fails to Predict Robust Subspace RecoveryPreprint
Jia, H., & Vijayaraghavan, A. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2603.02594 · Cited by 4
Apte, A., Khan, A., Farhi, E., Marwaha, K., Boulebnane, S., & Shaydulin, R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2609.39042 · Cited by 4
Dynamical cavity method for hypergraphs and its application to quenches in the k − XOR − SAT problem
Maier, A., Behrens, F., & Zdeborová, L. (2025) · Physical review. E · doi:10.1103/physreve.112.014306 · Cited by 3
Parametric RDT Approach to Computational Gap of Symmetric Binary Perceptron
Stojnic, M. (2026) · Journal of Statistical Physics · doi:10.1007/s10955-026-03689-w · Cited by 3
A CLuP algorithm to practically achieve ∼ 0.76 SK–model ground state free energy
Stojnic, M. (2025) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ae2091 · Cited by 3
The maximum-average subtensor problem: Equilibrium and out-of-equilibrium properties
Erba, V., Kupferschmid, N. M., Ortiz, R. P., & Zdeborová, L. (2026) · SciPost Physics · doi:10.21468/scipostphys.20.3.073 · Cited by 3
The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers
Gamarnik, D., & Kızıldağ, E. C. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834647 · Cited by 3
Self-citationUniformly Random Colourings of Sparse Graphs
Hurley, E., & Pirot, F. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585242 · Cited by 3
Phase diagram of compressed sensing with ℓ 0 -norm regularization
Barbier, D., Lucibello, C., Saglietti, L., Krząkała, F., & Zdeborová, L. (2025) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/adca21 · Cited by 3
Strong Low Degree Hardness for the Number Partitioning ProblemPreprint
Mallarapu, R., & Sellke, M. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2505.20607 · Cited by 3
Very Persistent Random Walkers Reveal Transitions in Landscape Topology
Kent-Dobias, J. (2026) · Physical Review Letters · doi:10.1103/jvpw-csk7 · Cited by 2
ALGEBRAIC DYNAMICAL SYSTEMS FROM LDPC CODES SATISFY A STRONG NEGATION OF THE WEAK PINSKER PROPERTY
Austin, T., Bowen, L., & Shriver, C. (2025) · Journal of the Institute of Mathematics of Jussieu · doi:10.1017/s147474802510100x · Cited by 2
Are Neural Networks Collision Resistant?
Benedetti, M., Bogdanov, A., Malatesta, E. M., Mézard, M., Perrupato, G., Rosen, A., Schwartzbach, N. I., & Zecchina, R. (2026) · Physical Review X · doi:10.1103/6shh-9h5m · Cited by 2
Symmetric Perceptron with Random Labels
Kızıldağ, E. C., & Wakhare, T. V. (2023) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta59647.2023.10301203 · Cited by 2
Collision Resistance of Single-Layer Neural NetsPreprint
Benedetti, M., Bogdanov, A., Malatesta, E. M., Mézard, M., Perrupato, G., Rosen, A., Schwartzbach, N. I., & Zecchina, R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2606.03807 · Cited by 2
Quantum-informed surrogate sampling for combinatorial optimizationPreprint
Wybo, E., & Finžgar, J. R. (2026) · arXiv (Cornell University) · doi:10.48550/arxiv.2607.22372 · Cited by 2
Programming guide for solving constraint satisfaction problems with tensor networks
Gao, X., 李, X. 晓. L., & Liu, J.-G. (2025) · Chinese Physics B · doi:10.1088/1674-1056/adbee2 · Cited by 1
Lim, C. C., Choon, N. H., Hashim, U. R., & Hasan, M. H. (2025) · Bulletin of Electrical Engineering and Informatics · doi:10.11591/eei.v14i4.9058 · Cited by 1
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Bogdanov, A., Rosen, A., Vafa, N., & Vaikuntanathan, V. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800741 · Cited by 1
Physics of Local Optimization in Complex Disordered Systems
Shen, M., Ortíz, G., Dong, Z., Weigel, M., & Nussinov, Z. (2026) · Physical Review Letters · doi:10.1103/kcbw-6zkv · Cited by 1
Interacting copies of random-constraint satisfaction problems
Angelini, M. C., Budzynski, L., & Ricci‐Tersenghi, F. (2025) · Physical review. E · doi:10.1103/86dj-6w3r · Cited by 1
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
