Seminar Details
Some Easy Optimization Problems Have the Overlap-gap Property
- Start Date: October 1, 2025
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Shuangping Li - Yale University
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Presentation Type: Stand Alone Presentation
- Abstract:
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.