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 2026 will be held on Monday, 9 November 2026 in Rome, Italy, and will be co-located with DISC 2026. The workshop will be chaired by Alexandre Nolin.

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

Schedule

The schedule below is tentative.

ADGA program
9:00	talk 1	Matthias Bentert: Perfect and Ideal Network Resilience
10:00	talk 2	Giuseppe Antonio Di Luna: Content-Oblivious Computation
11:00	coffee break
11:25	talk 3	Sorrachai Yingchareonthawornchai: Recent advances in vertex connectivity algorithms
12:25	lunch
13:45	talk 4	Isabella Ziccardi: No Distributed Quantum Advantages for 3-Coloring Rooted Trees
14:45	talk 5	Maxime Flin: Quantum Advantage for Distributed Symmetry Breaking
15:40	coffee break
16:00	talk 6	Eun Jung Kim: A Tight Meta-theorem for LOCAL Certification of MSO2 properties within Bounded Treewidth Graphs
17:00	workshop ends

Invited Speakers

Matthias Bentert

TU Berlin

Matthias Bentert is a postdoctoral researcher in the Intelligent Networks group at TU Berlin. He received his PhD from TU Berlin in 2020 under the supervision of Rolf Niedermeier in the Algorithms and Computational Complexity group. He subsequently worked as a postdoc in the same group and for two years in the Algorithms group at the University of Bergen, Norway, as part of Saket Saurabh’s ERC project. His research focuses on algorithms, mostly on parameterized algorithms and the boundary between polynomial-time solvability and NP-hardness. He is particularly interested in applying theoretical algorithmic techniques to new domains, with previous work including scheduling, algorithmic differentiation, and network algorithms. You can find out more about him on his webpage.

Perfect and Ideal Network Resilience

Modern communication networks support local fast-rerouting mechanisms that react to link failures without first communicating failure information through the network's control plane. This allows them to respond orders of magnitude faster than traditional approaches, reducing packet loss and improving throughput.

Such mechanisms are based on static failover rules that are predefined at each node. A forwarding decision may depend on locally available information, such as the incoming port, the destination of the packet, and the status of incident links, but not on failures elsewhere in the network. Ideally, these local rules provide perfect resilience: every packet reaches its destination as long as its source and destination remain connected after the link failures. Perfect resilience, however, cannot always be achieved. In fact, there are networks on only five vertices for which no perfectly resilient routing exists.

A natural weaker goal is ideal resilience. If the underlying network is k-link-connected, we ask only that every packet be delivered whenever at most k-1 links fail. Whether ideal resilience can always be achieved remains an open problem.

In this talk, I will give an overview of positive and negative results on local network resilience and highlight some of the ideas behind their proofs. We will also encounter a curious complexity phenomenon: finding a perfectly resilient routing is possible in polynomial time, while verifying that a given routing is perfectly resilient is coNP-hard.

Giuseppe Antonio Di Luna

University of Rome – Sapienza

Giuseppe Antonio Di Luna is an Associate Professor at Sapienza University of Rome. His research spans distributed algorithms and systems, with particular interests in anonymous and dynamic networks, fault tolerance, and coordination among mobile agents. He earned his Ph.D. at Sapienza in 2015, studying counting in anonymous dynamic networks, and subsequently held postdoctoral positions at the University of Ottawa and Aix-Marseille University. He has served on numerous conference program committees and co-chaired the organization of EuroSys 2023.

Content-Oblivious Computation

What can a distributed system compute when messages convey no information beyond their arrival? This talk explores asynchronous networks in which an adversary may arbitrarily corrupt every message, while preserving its delivery. Communication then reduces to exchanging content-free pulses. I will survey the content-oblivious model, explain how reliable computation can nevertheless be achieved, and discuss the role of network connectivity and leader election. The talk will also highlight open questions in this interesting and extremely restricted model.

Maxime Flin

Aalto University

Maxime Flin is a postdoctoral researcher in Jukka Suomela's group at Aalto University, Finland. He received his PhD from Reykjavik University in 2025, advised by Magnús M. Halldórsson. He works on graph algorithms, especially graph coloring in distributed, streaming, and dynamic models.

Quantum Advantage for Distributed Symmetry Breaking

In this talk, I will present a constant-round quantum-LOCAL algorithm for 3-coloring directed cycles with high probability. This follows from the surprising fact that for every ε > 0, there exists a one-way one-round quantum-LOCAL algorithm coloring nodes with 20,000 colors such that, for each edge, its endpoints receive the same color with probability at most ε.

Eun Jung Kim

School of Computing, KAIST

Eun Jung Kim is an Associate Professor in the School of Computing at KAIST and a member of the Discrete Mathematics Group at the Institute for Basic Science (IBS). Her research focuses on parameterized algorithms, structural graph theory, and algorithmic applications in linear matroids. She received her PhD in Computer Science from Royal Holloway, University of London in 2010, and subsequently worked as a CNRS researcher in France from 2011 to 2023. She joined KAIST in January 2024.

A Tight Meta-theorem for LOCAL Certification of MSO2 properties within Bounded Treewidth Graphs

Abstract to be announced.

Sorrachai Yingchareonthawornchai

Institute for Theoretical Studies, ETH Zurich

Sorrachai Yingchareonthawornchai is a Junior Fellow at the Institute for Theoretical Studies at ETH Zurich. His research focuses on fast graph algorithms and combinatorial optimization, particularly graph connectivity and network design. He received his Ph.D. in Computer Science from Aalto University in 2023, where his dissertation received the School of Science’s Doctoral Thesis Award. Previously, he held postdoctoral positions at the Hebrew University of Jerusalem and the Simons Institute for the Theory of Computing at UC Berkeley.

Recent advances in vertex connectivity algorithms

Abstract to be announced.

Isabella Ziccardi

CNRS, IRIF, Université Paris Cité

Isabella Ziccardi is a CNRS Postdoctoral Researcher at IRIF in Paris. Her research focuses on distributed algorithms for systems with limited computational and communication capabilities, with a broader interest in distributed random processes on graphs. More recently, she has also been exploring quantum distributed computing.

She received her PhD from the University of L’Aquila, Italy, under the supervision of Andrea Clementi and Luciano Gualà. She subsequently joined Bocconi University in Milan as a postdoctoral researcher, where she worked in Luca Trevisan’s group.

No Distributed Quantum Advantages for 3-Coloring Rooted Trees

Abstract to be announced.