Seminar in Derandomization (WS 25/26)

The seminar will be held in a blocked format. At the start of the semester there will be an introductory class where we give a short overview of selected papers that we think might be suitable for this seminar. Of course you are free to suggest additional papers yourself that you find interesting. Every student then picks a paper to read. Since most of the papers in this field are complex, it will be enough to present a part of the results (to be discussed with your supervisor). There will not be regular lectures throughout the semester. Instead, all participating students are supposed to present their chosen paper at one fixed date at the end of the semester (the precise date will be discussed at the start of the semester).

Possible choices for the paper include (but are not limited to):

 

Parallelization (CONGEST / LOCAL)

Authors Year Paper Notes
Ghaffari, Harris & Kuhn 2018 On derandomizing local distributed algorithms  
Ghaffari & Kuhn 2018 Derandomizing Distributed Algorithms with Small Messages:
Spanners and Dominating Set
hitting sets,
min. dominating set
Censor-Hillel, Parter & Schwartzman 2020 Derandomizing local distributed algorithms under bandwidth restrictions  
Ghaffari & Kuhn 2021 Deterministic Distributed Vertex Coloring: 
Simpler, Faster, and without Network Decomposition
 
Faour, Ghaffari, Grunau, Kuhn & Rozhoň 2023 Local Distributed Rounding:
Generalized to MIS, Matching, Set Cover and Beyond
 
Ghaffari, Grunau & Rozhoň 2023 Work-Efficient Parallel Derandomization I: 
Chernoff-like Concentrations via Pairwise Independence
 

 

MPC & Congested Clique

Authors Year Paper Notes
Chang & Saranurak 2020 Deterministic Distributed Expander Decomposition and Routing
with Applications in Distributed Derandomization
Section 6
Czumaj, Davies & Parter 2020 Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space  
Coy & Czumaj 2022 Deterministic Massively Parallel Connectivity  
Giliberti & Parsaeian 2024 Massively Parallel Ruling Set Made Deterministic  
Coy, Czumaj, Davies & Mishra 2024 Parallel Derandomization for Coloring  

 

(approximate) k-wise indepedence & pseudorandom generators

Authors Year Paper Notes
Gopalan & Yehudayoff 2020 Concentration for Limited Independence via
Inequalities for the Elementary Symmetric
Polynomials
Theorem 1.9
Coy & Czumaj 2022 Deterministic Massively Parallel Connectivity Section 3
Coy, Czumaj, Davies & Mishra 2024 Parallel Derandomization for Coloring Pseudorandom generators used in MPC

 

Distributed complexity theory

Authors Year Paper Notes
Chang, Kopelowitz & Pettie 2016 An Exponential Separation between Randomized and
Deterministic Complexity in the LOCAL Model
Section 3