1. Some easy optimization problems have the overlap-gap property
- Author
-
Li, Shuangping and Schramm, Tselil
- Subjects
Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms ,Mathematics - Combinatorics ,Mathematics - Probability - Abstract
We show that the shortest $s$-$t$ path problem has the overlap-gap property in (i) sparse $\mathbf{G}(n,p)$ graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse $\mathbf{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., Comment: 29 pages
- Published
- 2024