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 (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.
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 2 February 2023
13:00
60 Minutes
Virtual talk
Virtual talk
Saarbrücken
Abstract
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
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
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
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 rsharma@mpi-inf.mpg.de.
Roohani Sharma, 01/30/2023 10:43
Roohani Sharma, 01/13/2023 18:40 -- Created document.
Roohani Sharma, 01/13/2023 18:40 -- Created document.