Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, December 08, 2022, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Christoph Grunau
In this talk, I will present a general distributed derandomization method which allows to locally round fractional solutions of graph problems. Roughly speaking, the method can transform fractional/probabilistic label assignments of the vertices into integral/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). Informally speaking, the method allows to efficiently derandomize randomized algorithms which only require pairwise independence. The method is used by the state-of-the art deterministic algorithms for problems such as maximal independent set or network decomposition, two of the most central problems in distributed computing. This is joint work with Salwa Faour, Mohsen Ghaffari, Fabian Kuhn and Václav Rozhoň.
Automatic MiSe System Software Version 1.4803M | admin login