Network Decomposition and Distributed Derandomization (Invited Paper)
METADATA ONLY
Loading...
Author / Producer
Date
2020
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We overview a recent line of work [Rozhoň and Ghaffari at STOC 2020; Ghaffari, Harris, and Kuhn at FOCS 2018; and Ghaffari, Kuhn, and Maus at STOC 2017], which proved that any (locally-checkable) graph problem that admits an efficient randomized distributed algorithm also admits an efficient deterministic distributed algorithm, thereby resolving several central and decades-old open problems in distributed graph algorithms. We present a short and self-contained version of the proofs, and conclude by discussing several related questions that remain open.
This article accompanies a keynote talk of the author at the International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2020. The writing is based on [24, 28, 45] and primarily targets non-experts.
Permanent link
Publication status
published
External links
Book title
Structural Information and Communication Complexity
Journal / series
Volume
12156
Pages / Article No.
3 - 18
Publisher
Springer
Event
27th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Distributed graph algorithms; Derandomization; Network decomposition; LOCAL model
Organisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)
Notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.
Funding
853109 - Distributed and Massively Parallel Graph Algorithms (EC)