Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 07, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Sebastian Brandt
At the heart of a recent lower bound for the distributed Lovász Local Lemma lies a speedup technique that transforms any distributed algorithm for one specific LLL problem into a one-round-faster algorithm for the same problem. In this talk, I will show that such a speedup exists for any locally checkable problem, with the difference that the problem the sped-up algorithm solves is not (necessarily) the same as the initial problem. This opens new and exciting possibilities for obtaining bounds for the complexity of locally checkable problems. We will see that our speedup technique has concrete applications: in particular, we will use it to obtain new deterministic and randomized lower bounds for Maximal Matching and Maximal Independent Set in the LOCAL model of distributed computing, improving on and complementing the two famous lower bounds by Linial [FOCS'87] and Kuhn, Moscibroda and Wattenhofer [PODC'04].
Automatic MiSe System Software Version 1.4803M | admin login