# Some easy optimization problems have the overlap-gap property

arXiv: https://arxiv.org/abs/2411.01836 · HTML: https://mlsanity.com/paper/2411.01836/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2024.

## Built on by (most cited first, 5 of 5)

- [Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT](https://mlsanity.com/paper/2506.19276/) (2025)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Phase transition of descending phase retrieval algorithms](https://mlsanity.com/paper/2506.18275/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

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.