ADGA 2023

12th Workshop on Advances in Distributed Graph Algorithms · L'Aquila · 9 October 2023

ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The program consists of six invited talks, which are aimed at the general DISC audience.

The talks are designed to cover general aspects of a research topic rather than to present a particular new result. Such aspects include the advances achieved in the topic, the main remaining objectives, the technical obstacles, etc.

ADGA 2023 will be held on Monday, 9 October 2023, and will be co-located with DISC 2023. For information about the registration, please go to the DISC 2023 registration page. The workshop will be chaired by Laurent Feuilloley.

For information on past and future ADGA workshops, see the web site of the ADGA workshop series.


ADGA programme
9:00 talk 1 Fabian Kuhn: Local Distributed Rounding: A Tool For Efficient Deterministic Distributed Symmetry Breaking
10:00 talk 2 Alexandre Nolin: Pseudorandomness: some distributed applications
11:00 coffee break
11:20 talk 3 Joel Rybicki: Approximate agreement on graphs revisited
12:30 lunch
14:00 talk 4 Eva Rotenberg: How to Colour a Changing Sparse Graph
15:00 talk 5 Ami Paz: Beyond Worst-Case Analysis of Dynamic Networks
16:00 coffee break
16:30 talk 6 Jara Uitto: Symmetry Breaking in Massive Graphs
17:30 workshop ends

Invited Speakers

[Fabian Kuhn]

Fabian Kuhn

University of Freiburg

Fabian Kuhn received the M.Sc. and Ph.D. degrees in computer science from ETH Zurich, Zurich, Switzerland, in 2001 and 2005, respectively. He afterwards spent time as a Postdoctoral Researcher with Microsoft Research Silicon Valley, ETH Zurich and MIT. He was an Assistant Professor with the University of Lugano, and in 2012, he joined the University of Freiburg, as a Full Professor.

Local Distributed Rounding: A Tool For Efficient Deterministic Distributed Symmetry Breaking

[Alexandre Nolin]

Alexandre Nolin

CISPA Helmholtz Center for Information Security

Alexandre Nolin is currently a postdoctoral researcher at CISPA in the group of Sebastian Brandt. Before that, he received a Ph.D. in Computer Science at Université Paris Cité, where he was advised by Sophie Laplante, and was a postdoctoral researcher at Reykjavik University, where he was hosted by Magnús M. Halldórsson. His current research interests primarily gravitate around distributed graph algorithms.

Pseudorandomness: some distributed applications

In the past few decades, pseudorandom objects, notably expander graphs, have been key ingredients of several results in various subareas of theoretical computer science. To name a few: Undirected Connectivity being in deterministic LOGSPACE, the existence of $O(\log n)$-depth sorting networks, and randomness-efficient error reduction.

In this talk, we will see a few important techniques from the area of pseudorandomness together with some applications in distributed computing. Our main application will be the compression of bandwidth-hungry primitives in models with congestion. Existential proofs often precede explicit constructions in the area of pseudorandomness, and we will discuss what it means for known algorithmic results using pseudorandom objects.

[Ami Paz]

Ami Paz

LISN - CNRS & Paris-Saclay University

Ami Paz is a research scientist (chargé de recherche) in CNRS, France. He is interested in distributed graph algorithms, topological methods in distributed computing, dynamic graph algorithms, and the theory of computing in general. Ami earned his PhD at the Technion, Israel, and was a postdoctoral researcher at IRIF, Paris, and the University of Vienna. He won the Best Paper Award in SSS'19, Best Paper Award and Best Student Paper Award in SODA'17, and the Best Student Paper Award in PODC'13.

Beyond Worst-Case Analysis of Dynamic Networks

Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In the case of dynamic networks, this technique aims to explain the gaps between real-world networks that function well despite being dynamic and the strong theoretical lower bounds for arbitrary networks. In this talk, I will present our recent applications of smoothed analysis to dynamic networks. Our work studies different models of adversarial behavior and concerns problems such as information propagation and load balancing.

Based on joint works with Seth Gilbert, Uri Meir, and Gregory Schwartzman

[Eva Rotenberg]

Eva Rotenberg

Technical University of Denmark

Eva Rotenberg enjoys graph algorithms of all flavours. One of Eva's more recent interests is the connections and transfer of techniques between computational models, such as between distributed and dynamic graphs. Eva is an associate professor at the Technical University of Denmark, and enjoys participating in collaborative research projects in various topics related to graphs, algorithms, or both.

How to Colour a Changing Sparse Graph

Graph colouring is one of the most fundamental graph questions, and has received attention in pracically every computational model. In this talk, we will revisit graph colouring in the dynamic setting, where the graph is subject to arbitrary, adversarial insertions and deletions of edges. We will see how an interplay between dynamic and distributed algorithms can be used to give improved algorithmic solutions to the problem: distributed algorithms with dynamic advice was used in [STOC'23] to obtain new colouring algorithms for dynamic graphs. The notion of distributed algorithms with (dynamic) advice may be of independent interest, and the talk will mention open problems and open research directions.

Based on joint work with: Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog, Krzysztof Nowicki, Chris Schwiegelshohn, and Carsten Thomassen.

[Joel Rybicki]

Joel Rybicki

Humboldt University of Berlin

Joel Rybicki is an assistant professor at Humboldt University of Berlin. His research interests range from distributed algorithms to modelling biological dynamics. Previously, he was a postdoctoral fellow at the Institute of Science and Technology Austria (ISTA) and University of Helsinki, and he completed his doctorate in Aalto University.

Approximate agreement on graphs revisited

Many distributed coordination problems requiring perfect agreement, such as consensus, are typically hard to solve in a fault-tolerant manner. However, agreeing on values that are close to one another can be considerably easier. A classic example is the problem of approximate agreement over real values, which can be solved deterministically in many asynchronous models of computing — even if some processes arbitrarily fail. In this talk, I discuss generalisations of approximate agreement to arbitrary undirected graphs. It turns out that the structure of the graph significantly influences both solvability and complexity of such problems. The talk will overview some recent results and open problems in the area.

[Jara Uitto]

Jara Uitto

Aalto University

Jara Uitto is an assistant professor at the Aalto University in Finland. Before moving to Finland, he was a postdoc in the group of Mohsen Ghaffari at ETH Zürich, where he also received his PhD in 2015 under the supervision of Roger Wattenhofer. His research interests lie in (massively) parallel and distributed graph algorithms.

Symmetry Breaking in Massive Graphs

Symmetry breaking problems, such as vertex coloring and maximal independent set (MIS), have recently received a lot of attention in the study of (massively) parallel graph algorithms. By now, a standard technique to approach these problems is to sparsify the input graph and to efficiently simulate a distributed message passing algorithm in the sparse graph. Especially for MIS, the progress is stuck in the sparsification step, and the current techniques seem insufficient to push forward. We discuss algorithms for graphs that are already sparse where the sparsification step becomes irrelevant and nevertheless, the problem remains hard. In this setting, we require new methods to obtain efficient algorithms. In this talk, we discuss new techniques that do not rely on graph sparsification and the recent developments on massively parallel algorithms for symmetry breaking problems.