Theory Seminar - Tselil Schramm April 25, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 7101 (Special Time) Speaker: TSELIL SCHRAMM , Assistant Professor, Department of Statistics, Stanford University https://tselilschramm.org/ Some easy optimization problems have the overlap-gap property An optimization problem is said to have the "overlap-gap property" (OGP) if the near-optimal solutions are partitioned into several well-separated clusters. 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.Faculty Host: Ryan O'Donnell Add event to Google Add event to iCal
