Some easy optimization problems have the overlap-gap property

2024/11/04 by Li, Shuangping, Schramm, Tselil · 6 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2411.01836

Abstract

We show that the shortest s-t path problem has the overlap-gap property in (i) sparse G(n,p) graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse G(n,p) graphs, shortest path is solved by O(log n)-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem.

Cited by

• Binary perceptron computational gap -- a parametric fl RDT view
• Sharp Online Hardness for Large Balanced Independent Sets
• Polynomial-time sampling despite disorder chaos
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• Phase transition of descending phase retrieval algorithms
• Overlap Gap and Computational Thresholds in the Square Wave Perceptron

Related

• Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential
• First Passage Percolation with Queried Hints
• Approximating the shortest path problem with scenarios
• The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
• Shortest Paths with Linear Edge Weights