Dagstuhl-Seminar 24471
Graph Algorithms: Distributed Meets Dynamic
( 17. Nov – 22. Nov, 2024 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/24471
Organisatoren
- Keren Censor-Hillel (Technion - Haifa, IL)
- Yasamin Nazari (VU Amsterdam, NL)
- Eva Rotenberg (Technical University of Denmark - Lyngby, DK)
- Thatchaphol Saranurak (University of Michigan - Ann Arbor, US)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Jutka Gasiorowski (für administrative Fragen)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
In modern computational systems, the need to handle large-scale inputs imposes interesting computational challenges. Two such challenges are (1) the need to distribute the computation over multiple units, and (2) the dynamic nature of the input, which may undergo changes over time. A particular class of problems studied in these settings is when the input to the computational task is a huge graph.
The field of dynamic graph algorithms addresses efficiently processing edge/vertex insertions/deletions in the input graph. In distributed graph algorithms, the input resides across multiple machines, and the goal is to solve the problem while minimizing the number of rounds of communication. Both of these rich research areas have been extensively studied since at least the 1980’s. We know of efficient algorithms for a large variety of tasks, such as shortest paths problems, coloring, subgraph finding, symmetry breaking, approximations, and many more. However, there are still fundamental problems with no known efficient solutions in some of these models, and even more where the exact complexity of computation is yet to be determined. In the recent years, a number of influential works show how transferring ideas from one of these models to the other provides progress on some of the long-lasting open problems.
The goal of this Dagstuhl Seminar is to build a bridge between the two research communities of dynamic graph algorithms and distributed computing, by working together on joint research frontiers. The aim is to provide a pivotal ground for future growth of these thriving areas:
- Transfer of knowledge between the dynamic and distributed settings both on the algorithms (upper bound) and complexity (lower bound) side. Some problems in which this shared knowledge has shown potential are: shortest paths, matching, maximal independent set, coloring, clustering, and flows. For some of these areas there are already common toolkits being utilized such expander decomposition, low diameter network decomposition, algebraic tools, distance and cut sparsification, and sketching tools. This common toolkit suggests a concrete way forward for transferring ideas. We will explore tools and ideas for improved algorithms, and we will exchange knowledge about techniques for proving lower bounds, which are an essential component of understanding the computational abilities of any model of computation.
- Advancing the landscape of fast algorithms for the combined distributed dynamic setting. This setting is very natural, and very well-motivated by practice. While there has been some recent work in this direction, there is still very little known on this overlapping setting. New solutions in such a model may even improve the state-of-the-art for some problem in more than one model; for instance, an adaptive dynamic distributed algorithm may be useful as a subroutine for a static distributed algorithm.
Creative Commons BY 4.0
Keren Censor-Hillel, Yasamin Nazari, Eva Rotenberg, and Thatchaphol Saranurak
Please log in to DOOR to see more details.
- Sepehr Assadi
- Alkida Balliu
- Aaron Bernstein
- Sayan Bhattacharya
- Joakim Blikstad
- Sebastian Brandt
- Karl Bringmann
- Keren Censor-Hillel
- Yi-Jun Chang
- Shiri Chechik
- Keerti Choudhary
- Martin Costa
- Tijn de Vos
- Michal Dory
- Aditi Dudeja
- Faith Ellen
- George Giakkoupis
- Seth Gilbert
- Christoph Grunau
- Magnús M. Halldórsson
- Adam Karczmarz
- Fabian Daniel Kuhn
- Jakub Lacki
- Quanquan C. Liu
- Yannic Maus
- Danupon Nanongkai
- Yasamin Nazari
- Alexandre Nolin
- Krzysztof Nowicki
- Dennis Olivetti
- Ami Paz
- Richard Peng
- Vijaya Ramachandran
- Eva Rotenberg
- Thatchaphol Saranurak
- Shay Solomon
- Jukka Suomela
- Jan van den Brand
- Virginia Vassilevska Williams
- David Wajc
- Tianyi Zhang
- Anna Zych-Pawlewicz
Klassifikation
- Data Structures and Algorithms
- Discrete Mathematics
- Distributed / Parallel / and Cluster Computing
Schlagworte
- Algorithms design and analysis
- dynamic graphs
- distributed graph algorithms
- algorithmic complexity
