Distributed Algorithms Seminar
Summer Term 2025
Seminar topic: Derandomization in Distributed and Parallel Algorithms
The goal of derandomization is to convert a randomized algorithm into a deterministic one that gives "similar" guarantees without relying on random choices. In this seminar we will mainly focus on derandomizing algorithms in distributed models such as the LOCAL or CONGEST model and in parallel models such as the the classic PRAM model or the massively parallel computation (MPC) model.
Seminar description
To pass the seminar, each student participating in the seminar has to present one paper (the list of possible papers will soon be published on this webpage). The presentations about each paper will be 45 minutes (approx. 60 mins including questions) so that we have enough time to dive into the papers in sufficient detail to really understand what is going on. For the talks, we will have three meetings on the last three Fridays of the semester, each time in the afternoon from 13:15 - 17:00 (i.e., on July 11, 18, and 25). Attendance to those meetings is mandatory to pass the seminar. In the first week on Friday, 25.04., from 12:15 - 14:00 in room 101-01-016/18, there will be an introductory meeting to the seminar, where we will explain our plan for the seminar in more detail.
Note that you have to sign up to the seminar through HISinOne. The process of how to sign up for seminars and how the assignment of the seminar slots is organized is decribed here.
Topics and Schedule
Here is the list of the topics of the seminar and also the days on which the talks about those topics are supposed to take place.
Friday, 11.07.2025, 13:15 - 17:30: Presentations I (in room 51-00-006)
- The method of conditional probabilities in the classic
centralized setting applied to the derandomization of the randomized
rounding solutions of integer linear programs. This is for example
nicely described in the following paper of Araving Srinivasan:
Improved approximations of packing and covering problems.
(presented by Bardia Dorry, supervised by Attila Mályusz) - A Simple Parallel
Algorithm for the Maximal Independent Set Problem by Michael
Luby. The paper contains a classic randomized parallel algorithm for
computing a maximal independent set of a graph and it also describes
how to remove the randomness from the algorithm.
(presented by Josephine Bergmeier, supervised by Marc Fuchs) - Locality in
Distributed Graph Algorithms by Nathan Linial
and Weak graph colorings: distributed algorithms and applications by
Fabian Kuhn. The papers
describe fast deterministic distributed coloring algorithms that
will be important building blocks for derandomizing distributed
algorithms. The second paper uses techniques from the first paper
and adapts them to more general forms of graph coloring. The
papers also show how the one can use probabilisit methods to
directly design deterministic algorithms.
(presented by Ruben Rosenmeyer, supervised by Gustav Schmid) - Distributed construction of network decompositions. We want to
primarily cover the deterministic algorithm from A Simple
Deterministic Distributed Low-Diameter Clustering by Rozhoň,
Häupler, and Grunau. Possibly, one can also cover the idea
of the randomizaed algorithm from Distributed
Strong Diameter Network Decomposition by Elkin and Neiman.
(presented by Hossein Salehi Vaziri, supervised by Gustav Schmid)
Friday, 18.07.2025, 13:15 - 17:30: Presentations II (in room 51-00-006)
- Generic derandomization of randomized distributed algorithms in
the LOCAL model by using the method of conditional
expectation. Paper On
Derandomizing Local Distributed Algorithms by Ghaffari,
Harris, and Kuhn.
(presented by Veronika Klasen, supervised by Attila Mályusz) - Deterministic distributed maximal independent set algorithm with
small messages: Derandomizing
local distributed algorithms under bandwidth restrictions by
Censor-Hillel, Parter, and Schwartzman.
(presented by Erik Kassubek, supervised by Marc Fuchs) - Very fast
deterministic coloring algorithm in a bandwidth-restricted
all-to-all communication
model: Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC by Czumaj,
Davies, and Parter
(presented by Selin KeleÅŸ, supervised by Zahra Parsaeian) - Deterministic ruling set computation in the massively parallel
computation (MPC) model: Massively Parallel Ruling Set
Made Deterministic by Giliberti and Parsaeian.
(presented by Shivani Sharma, supervised by Zahra Parsaeian)
Friday, 25.07.2025, 13:15 - 17:30: Presentations III (in room 51-00-006)
- A more lightweight method to derandomize some distributed
algorithms. The paper Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond by Faour, Ghaffari, Grunau,
Kuhn, and Rozhoň describes how to gradually round a given
fractional (randomized) solution to certain problems to an almost equally good
deterministic solution
(presented by Max Gölz, supervised by Salwa Faour) - Using gradual rounding to obtain a faster network decomposition
algorithm (and faster algorithms for other
problems): Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
by Ghaffari, Grunau, Häupler, Ilchi, and Rozhoň.
(presented by Oguz Kuyucu, supervised by Salwa Faour) - Faster distributed algorithms for computing maximal independent sets and
matchings: Faster
Deterministic Distributed MIS and Approximate Matching The
paper combines several of the techniques of the above papers to
obtain faster algorithms for some specific problems.
(presented by tba., supervised by Gustav Schmid) - Parallel derandomization of Chernoff
bounds: Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence
by Ghaffari, Grunau, and Rozhoň
(presented by tba., supervised by Zahra Parsaeian)