The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures

Abstract

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 possible. At the same time the formal hardness of these problems in form of say complexity-theoretic $NP$-hardness is lacking. In this introductory article a new approach for algorithmic intractability in random structures is described, which is based on the topological disconnectivity property of the set of pair-wise distances of near optimal solutions, called the Overlap Gap Property. The article demonstrates how this property a) emerges in most models known to exhibit an apparent algorithmic hardness b) is consistent with the hardness/tractability phase transition for many models analyzed to the day, and importantly c) allows to mathematically rigorously rule out large classes of algorithms as potential contenders, in particular the algorithms exhibiting the input stability (insensitivity).

arXiv comment26 pages, 6 figures, 1 table

References in corpus (26)

• A Quantum Approximate Optimization Algorithm
• The Loss Surfaces of Multilayer Networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Learning by message-passing in networks of discrete synapses
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Local algorithms for independent sets are half-optimal
• A better algorithm for random k-SAT
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Suboptimality of local algorithms for a class of max-cut problems
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Disorder chaos and multiple valleys in spin glasses
• Analysis of the Karmarkar-Karp Differencing Algorithm
• Walksat stalls well below the satisfiability threshold
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Biased landscapes for random Constraint Satisfaction Problems
• Proof of the satisfiability conjecture for large k
• Clustering of solutions in the symmetric binary perceptron
• Analysing Survey Propagation Guided Decimation on Random Formulas
• Computing the partition function of the Sherrington-Kirkpatrick model is hard on average
• Balancing Gaussian vectors in high dimension
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• The Overlap Gap Property and Approximate Message Passing Algorithms for $p$-spin models
• Shattering Versus Metastability in Spin Glasses

Cited by in corpus (47)

• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Challenges and Opportunities in Quantum Optimization
• NLTS Hamiltonians from good quantum codes
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Quantum-Informed Recursive Optimization Algorithms
• Disordered Systems Insights on Computational Hardness
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert
• Energy landscapes of combinatorial optimization in Ising machines
• Hard Optimization Problems have Soft Edges
• Revisiting the Challenges of MaxClique
• Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• (Dis)assortative Partitions on Random Regular Graphs
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models
• On the free energy of vector spin glasses with non-convex interactions
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Statistical mechanics of the maximum-average submatrix problem
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Combinatorial NLTS From the Overlap Gap Property
• Gap Amplification for Reconfiguration Problems
• On the topology of solutions to random continuous constraint satisfaction problems
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
• The Overlap Gap Property limits limit swapping in the QAOA
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Algebraic dynamical systems from LDPC codes satisfy a strong negation of the weak Pinsker property
• Uniformly Random Colourings of Sparse Graphs
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• Ground States of the Mean-Field Spin Glass with 3-Spin Couplings
• Quantum Glassiness From Efficient Learning
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
• Interacting Copies of Random Constraint Satisfaction Problems
• Maximum Consensus by Weighted Influences of Monotone Boolean Functions
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression