Some Easy Optimization Problems Have the Overlap-Gap Property
Abstract
We show that the shortest $s$-$t$ path problem has the overlap-gap property in (i) sparse $\mathbb{G}(n,p)$ graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse $\mathbb{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.
Cite
Text
Li and Schramm. "Some Easy Optimization Problems Have the Overlap-Gap Property." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.Markdown
[Li and Schramm. "Some Easy Optimization Problems Have the Overlap-Gap Property." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.](https://mlanthology.org/colt/2025/li2025colt-some/)BibTeX
@inproceedings{li2025colt-some,
title = {{Some Easy Optimization Problems Have the Overlap-Gap Property}},
author = {Li, Shuangping and Schramm, Tselil},
booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory},
year = {2025},
pages = {3582-3622},
volume = {291},
url = {https://mlanthology.org/colt/2025/li2025colt-some/}
}