Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 29, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Sebastian Brandt
Recently [STOC '16], the best known lower bound for the distributed Lovász Local Lemma was improved from \Omega(log* n) to \Omega(log log n) by using a new lower bound technique based on the idea that, under certain circumstances, the existence of an algorithm implies the existence of a faster algorithm. This discovery led to other results, among them an exponential separation between randomized and deterministic complexity in the LOCAL model [FOCS '16]. Very recently [SODA '18], a refinement of said technique appeared in the context of edge colorings, facilitating a simpler analysis of the involved speed-up step. In this talk, we will take an in-depth look at the idea behind the lower bound technique and examine its simplified version.
Automatic MiSe System Software Version 1.4803M | admin login