Shortest paths without a map, and the randomized k-server conjecture

The talk is about two papers, both of which are joint work with Sébastien Bubeck (Microsoft Research) and Yuval Rabani (Hebrew University) and resolve some long-standing open problems in online computing.

In the first, “Shortest paths without a map, but with an entropic regularizer” (FOCS 2022), we consider an online version of the shortest paths problem, introduced by Papadimitriou and Yannakakis in 1989. In this version of shortest paths, the graph is initially unknown and revealed layer by layer over time. We give an O(k^2)-competitive algorithm, where k is the maximal number of vertices in a layer. The result is optimal and the first improvement since 1993 on the previous bound of O(k^13).

In the second, “The randomized k-server conjecture is false!” (to appear), we give an Omega((log k)^2) lower bound on the competitive ratio of randomized algorithms for the k-server problem. This refutes the folklore conjecture that an O(log k)-competitive algorithm exists for all metric spaces (which is known to exist for some metric spaces). The result also implies improved lower bounds for some other problems. In particular, for metrical task systems our lower bound matches the existing upper bound, and it is the first improvement of the lower bound since the introduction of the model 35 years ago (in 1987).