Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The landscape of distributed time complexity
Speaker:Jukka Suomela
coming from:Aalto University
Speakers Bio:Jukka Suomela ( is an Assistant Professor in the Department of Computer Science at Aalto University. His work focuses on the theoretical foundations of distributed computing, with particular emphasis on the concept of locality. He is a member of the EATCS council, he was recently a local co-chair of ALGO 2018, and he is the PC chair of DISC 2019.
Event Type:AG1 Mittagsseminar (others' work)
Visibility:D1, D3, D4, RG1, MMCI, D2, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 14 March 2019
Duration:30 Minutes
Building:E1 4
Our understanding of the landscape of the computational complexity in distributed systems has changed a lot in the recent years, and one of the most successful concepts that has been driving this development is "locally checkable labelings" (LCLs).

In brief, LCLs are graph problems in which feasible solutions can be recognized by checking the constant-radius neighborhood of each node. For example, coloring a graph with 3 colors is an LCL: if each node is labeled with one of three colors and there are no conflicts in any local neighborhood, then the solution is also globally feasible. Other examples of LCLs include numerous constraint satisfaction problems on graphs, as well as problems such as maximal independent sets and minimal dominating sets.

Informally, LCL problems can be seen as a distributed analogue of the complexity class NP: given a feasible solution, it is easy to verify it in a distributed manner. But what can we say about the computational complexity of finding a solution in a distributed manner?

The concept of LCLs was introduced by Naor & Stockmeyer in 1995, and they also initiated the study of the distributed complexity of LCL problems. However, for 20 years since their seminal work, the landscape of the computational complexity of LCL problems looked somewhat barren. There were examples of LCL problems with only three distinct time complexities!

All of this changed around year 2016. Since then, we have seen a large number of papers that have formed a comprehensive and unexpectedly rich picture of the distributed complexity landscape of LCL problems.

In this talk I will tell more about the research area, what we now know about the topic, and what are the key open questions at the moment.

Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Christoph Lenzen, 02/04/2019 05:22 PM
Last modified:
Uwe Brahm/MPII/DE, 03/14/2019 07:01 AM
  • Christoph Lenzen, 02/04/2019 05:22 PM -- Created document.