Distributed Exact Weighted All-Pairs Shortest Paths

p>A fundamental question in distributed computing is how fast a network can compute shortest paths. This question has been extensively studied in the CONGEST model, where a network is modeled by an n-vertex m-edge graph. Each vertex represents a processor. The communication proceeds in synchronized rounds, with an O(log n)-bit message size constraint.

In this talk, I will present a STOC'17 paper (by Huang, Nanongkai, and Saranurak, arXiv:1708.03903), which shows an O(n^{5/4} poly log n)-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive O(m)-time algorithm when the network is not so sparse.