Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 31, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Yi-Jun Chang
In this talk, we consider solving locally checkable labeling (LCL) problems (i.e., the graph problems whose solution can be verified locally, such as maximal independent set and proper k-coloring) in the LOCAL model of distributed computing. Starting in 2016, there is a line of research that aims at understanding the computational complexity of LCL problems on bounded-degree graphs. An interesting finding of this research is the existence of several "gaps" in the complexity landscape. For example, in [Chang, Kopelowitz, Pettie, FOCS 2016], we showed that any LCL problem on bounded-degree graphs has deterministic round complexity either O(log* n) or Omega(log n). However, many of these proofs are "non-constructive" in the sense that they do not provide an algorithm that decides which side of the gap a given LCL problem belongs to. In this talk, we will show that using a connection between LCL and automata theory, it is possible to make some of these results "constructive."
Automatic MiSe System Software Version 1.4803M | admin login