On the stability of shortest path algorithms

Optimization problems on random instances frequently appear in statistics and theoretical computer science, and many of them appear to be hard to solve with efficient algorithms. The overlap gap property (OGP) was introduced to predict the hardness of random optimization, which is a rigorous barrier to the success of stable algorithms. However, it was recently shown that the shortest path problem on sparse random graphs exhibits the OGP, which implies that "elementary" efficient shortest path algorithms are not stable. In this talk, I will use this shortest path example to demonstrate how shifting the optimization landscape might alter the presence of the OGP and the stability of algorithms, which also raises important questions on the interpretation of the OGP. This is based on joint work with Frederic Koehler.