Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, November 09, 2021, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Vaclav Rozhon
It is an important statement in the theory of distributed computing that deterministic algorithms that color a Delta-regular tree with Delta colors need at least log(n) time to finish. It was proven by Brand et al. in 2016 but, funnily enough, it also directly follows from a set theoretical result proven by Marks in 2013. I will explain (a finite version of) Marks' proof and maybe talk about some recent developments around it that are joint with Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, and Zoltán Vidnyánszky.
Automatic MiSe System Software Version 1.4803M | admin login