Connections Workshop: Probability and Statistics of Discrete Structures: Some easy optimization problems have the overlap-gap property
Presenter
January 23, 2025
Keywords:
- random graphs
- network inference
- phase transitions
- probabilistic combinatorics
- Markov Chain Monte Carlo
MSC:
- 05C80 - Random graphs (graph-theoretic aspects)
Abstract
An optimization problem is said to have the "overlap-gap property" (OGP) if the near-optimal solutions are clustered in a particular way. In statistical physics, the overlap gap property is associated with computational intractability for optimization. Further, variants of the OGP imply unconditional lower bounds against local and/or Lipschitz algorithms. In recent years, the OGP has been accepted by some as a good heuristic for predicting computational intractability, even beyond these specific unconditional lower bounds. In this talk, I'll demonstrate that the shortest path problem in sparse random graphs has the OGP. Because shortest path is computationally easy, this complicates the picture for the overlap-gap property. Based on joint work with Shuangping Li.