Locality in online, dynamic, sequential, and distributed graph algorithms
Suomela Jukka
Aalto University, Finland
AG1 Mittagsseminar (own work)
Jukka Suomela (https://jukkasuomela.fi/) is Associate Professor in the Department of Computer Science at Aalto University, Finland. His work focuses on the theoretical foundations of distributed and parallel computing, with particular emphasis on the concept of locality. He was the PC chair of DISC 2019 and SIROCCO 2016 and one of the local chairs of ALGO 2018, he is serving in the EATCS council, and he is currently the chair of the DISC steering committee. He has received the FOCS 2019 best paper award and DISC 2012 and 2017 best paper awards, as well as a number of teaching awards.
I will discuss the notion of locality in the context of graph problems, from four different perspectives: online graph algorithms, dynamic graph algorithms, sequential distributed algorithms, and parallel distributed algorithms.
I will use the graph coloring problem as a running example, and I will explore settings like this:
- Online graph algorithms: The adversary reveals the graph one node at a time. How far do you need to see around a node until it is safe to pick its color?
- Dynamic graph algorithms: The adversary constructs the graph one edge at a time, and you need to maintain a valid coloring after each addition. How far around the new edge do you need to modify the solution?
- Distributed graph algorithms: Each node has to choose its own color simultaneously in parallel based on its local neighborhood. How far does it need to see?
While these are different questions in general, we can show that there are families of graph problems for which all these notions are equal to each other.
This talk is based on joint work with Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, and Joona Särkijärvi, and there is a manuscript available athttps://arxiv.org/abs/2109.06593