Mohsen Ghaffari: Improved Local Distributed Graph Algorithms

Abstract:  How can the computers in a network interact and communicate to solve the network's graph problems efficiently?

This is the subject of the area of (local) distributed graph algorithms, which dates back to the 1980s. The recent years have witnessed significant developments in this classical area.

1) On the randomized side, we present the first nearly-optimal randomized distributed algorithm for maximal independent set. Using well-known reductions, this provides a unified efficient algorithm for all the classical problems of the area.

2) On the deterministic side, we present an improved deterministic distributed algorithm for edge coloring, which almost settles a quarter-century old open problem.

3) We conclude with mentioning a surprising result that pinpoints the gap between randomized and deterministic algorithms: we present a rudimentary-looking rounding problem, which admits a trivial 0-round random algorithm, and prove that if one can solve it deterministically in polylog(n) rounds, we would get polylog(n)-round deterministic distributed algorithms for all the local problems. The latter remains the most well-known open question of the area.