Campus Event Calendar

Event Entry

What and Who

Locality in online, dynamic, sequential, and distributed graph algorithms

Suomela Jukka
Aalto University, Finland
AG1 Mittagsseminar (own work)

Jukka Suomela ( 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.
AG 1  
AG Audience

Date, Time and Location

Thursday, 2 February 2023
60 Minutes
Virtual talk
Virtual talk


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 at


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

974 6298 9871
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk, but do not have the password, contact Roohani Sharma at

Roohani Sharma, 01/30/2023 10:43
Roohani Sharma, 01/13/2023 18:40 -- Created document.