Campus Event Calendar
Event Entry
What and Who
The landscape of distributed time complexity
Jukka Suomela
Aalto University
AG1 Mittagsseminar (others' work)
Jukka Suomela (https://users.ics.aalto.fi/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.
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 14 March 2019
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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.
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.
Contact
Christoph Lenzen
--email hidden
passcode not visible
logged in users only
Christoph Lenzen, 02/04/2019 17:22 -- Created document.