Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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."

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login