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)

1. 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.
2. 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.
3. 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.
4. 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.

Friday, 18.07.2025, 13:15 - 17:30: Presentations II (in room 51-00-006)

5. 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.
6. Deterministic distributed maximal independent set algorithm with small messages: Derandomizing local distributed algorithms under bandwidth restrictions by Censor-Hillel, Parter, and Schwartzman.
7. 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
8. Deterministic ruling set computation in the massively parallel computation (MPC) model: Massively Parallel Ruling Set Made Deterministic by Giliberti and Parsaeian.

Friday, 25.07.2025, 13:15 - 17:30: Presentations III (in room 51-00-006)

9. 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
10. 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ň.
11. 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.
12. Parallel derandomization of Chernoff bounds: Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence by Ghaffari, Grunau, and Rozhoň