Mohsen Ghaffari: Improved Local Distributed Graph Algorithms

Tuesday, September 27, 2016 - 4:00pm to 5:00pm
Light Refreshments at 3:50pm
Patil/Kiva G449
Mohsen Ghaffari, MIT

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.

​In this talk, we​ survey some of these developments. Noting the gap between randomized and deterministic distributed graph algorithms, the talk has three (closely-related) parts:

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.