Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Network Decomposition and Derandomization for Distributed Algorithms
Speaker:Mohsen Ghaffari
coming from:ETH Zurich
Speakers Bio: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.

Event Type:Talk
Visibility:D1, D3, D4, RG1, MMCI, D2, INET, D5, SWS
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Thursday, 14 November 2019
Duration:60 Minutes
Building:E1 4
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.
Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Christoph Lenzen, 11/11/2019 01:47 PM
  • Christoph Lenzen, 11/11/2019 01:46 PM -- Created document.