Some easy optimization problems have the overlap-gap property
Introductory Workshop: Probability and Statistics of Discrete Structures January 27, 2025 - January 31, 2025
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Primary Mathematics Subject Classification
No Primary AMS MSC
Secondary Mathematics Subject Classification
No Secondary AMS MSC
Spectral Clustering in the Gaussian Mixture Block Model
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.
This is based on joint work with Tselil Schramm.
Spectral Clustering in the Gaussian Mixture Block Model
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.