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):
| 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 |
| 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 |
| 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 |
| Authors | Year | Paper | Notes |
| Chang, Kopelowitz & Pettie | 2016 | An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model |
Section 3 |
