Mohsen Ghaffari is an assistant professor of computer science at
ETH Zurich. He joined ETH after receiving a PhD from MIT. Mohsen has a broad range of interests in theoretical computer science, with a focus on distributed algorithms, parallel algorithms, and network algorithms. His work has been recognized with several prestigious awards including MIT's 2017 Sprowls award of best thesis in computer science, ACM's 2017 Principles of Distributed Computing dissertation award, and an honorable mention of ACM's 2017 doctoral dissertation award, as well as seven best paper or best student paper awards at top theory and distributed computing conferences, a 2019 ERC starting grant, and a 2019 Google's faculty research award.

AG 1, AG 3, AG 4, RG1, MMCI, AG 2, INET, AG 5, SWS   Info

MPI Audience

English

60 Minutes

Saarbrücken

We present an efficient deterministic distributed algorithm
for network decomposition and explain how this implies a general
distributed derandomization theorem, proving that PLOCAL=P-RLOCAL.
That is, informally, any efficient (i.e., polylogarithmic-time)
randomized distributed algorithm for any locally checkable graph
problem can be derandomized to an efficient deterministic distributed
algorithm. This leads to near-exponential improvements in
deterministic and, perhaps surprisingly, randomized distributed
algorithms for numerous graph problems, as well as some improvements
for massively parallel algorithms (i.e., MapReduce). These results
settle several decades-old and central open problems in distributed
graph algorithms, including Linial's well-known MIS question
[FOCS'87], which had been called the most outstanding problem in the
area. This is based on joint work with my student Vaclav Rozhon.

Christoph Lenzen

--email hidden

passcode not visible

logged in users only