Some easy optimization problems have the overlap-gap property

Zoom Link

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.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.