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):

Authors Year Paper Topic
Ghaffari, Grunau & Rozhoň 2023 Work-Efficient Parallel Derandomization I. Chernoff-like Concentrations via Pairwise Independence parallel derandomization
Ghaffari, Harris & Kuhn 2018 On derandomizing local distributed algorithms generic derandomization via SLOCAL
Chang, Kopelowitz & Pettie 2016 An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model complexity theory
Censor-Hillel, Parter & Schwartzman 2020 Derandomizing local distributed algorithms under bandwidth restrictions congested clique model
Ghaffari & Kuhn 2021 Deterministic Distributed Vertex Coloring. Simpler, Faster, and without Network Decomposition local rounding
Ghaffari & Kuhn 2018 Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set method of conditional expectation
Chang & Saranurak 2020 Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization distributed expander decompositions