EECS Special Seminar: Mohsen Ghaffari "Recent Advances in Distributed Graph Algorithms"

Abstract: Distributed systems are ubiquitous nowadays, e.g., computer networks, multi-core machines, and robot swarms. With the constant increase in the size of networks and datasets, distributed systems will arguably play an even greater role in the future. A wide range of fundamental problems in distributed systems can be formulated mathematically as graph problems. Distributed graph algorithms provide efficient methods that enable the autonomous entities of a distributed system to collaboratively solve these problems.

In this talk, I will overview some of the recent developments in distributed graph algorithms. In particular, I will discuss a new complexity-theoretic perspective on the issue of deterministic versus randomized distributed graph algorithms, an issue that underlies arguably the most well-known open question in this area. I will explain how this perspective reduces the whole issue to just one simple-looking problem. By solving special cases of this overarching problem, we have been able to obtain improvements in distributed algorithms for several well-studied problems, for both deterministic and (perhaps surprisingly) randomized algorithms. In a number of cases, this has led to resolutions of central and decades-old open questions.

Bio: Mohsen Ghaffari is an assistant professor in the computer science department of ETH Zurich. Before joining ETH in 2016, he received his PhD from MIT. Mohsen's research revolves around the theory of distributed computing, especially distributed graph algorithms and network algorithms. His work has been recognized by several awards, including seven best paper and best student paper awards at SODA/PODC/DISC/ICALP conferences and a number of doctoral dissertation awards.