Abstracts and slides
(CNRS and Universit茅 Paris Cit茅)
Algorithmic Meta-Theorems for Distributed Computing
-
Algorithmic meta-theorems can be viewed as theorems applying to large classes of algorithmic problems at once. An archetypal example of algorithmic meta-theorems is Courcelle's theorem (1990), which states that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. Such a theorem is remarkable for many reasons, in particular for it establishes tight connections between sequential algorithms complexity, graph theory, and logic. It is only recently that meta-theorems have been formulated for distributed computing. This talk will survey some of the recent contributions in this field. In particular, it will address distributed decision for graph properties definable in first-order logic in graphs of bounded expansion, and distributed certification for graph properties definable in monadic second-order logic in graphs of bounded treewidth, as well as in graphs of bounded clique-width.
- Slides
The Semi-Robust Communication Complexity of Maximum Matching
-
In this talk, we study the one-way two-party communication complexity of Maximum Matching in the semi-robust setting where the edges of a maximum matching are randomly partitioned between Alice and Bob, but all remaining edges of the input graph are adversarially partitioned between the two parties. We show that the simple protocol where Alice solely communicates a lexicographically-first maximum matching of their edges to Bob is surprisingly powerful: We prove that it yields a 3/4-approximation in expectation and that our analysis is tight.
- Slides
(Gran Sasso Science Institute (GSSI))
Distributed Algorithms for Local Potential Problems
-
In this talk, we present a fast distributed algorithm for local potential problems: these are graph problems where the task is to find a locally optimal solution where no node can unilaterally improve the utility in its local neighborhood by changing its own label. A simple example of such a problem is the task of finding a locally optimal cut, i.e., a cut where for each node at least half of its incident edges are cut edges.
The distributed round complexity of the locally optimal cut problem has been wide open; the problem is known to require 惟(log n) rounds in the deterministic LOCAL model and 惟(loglog n) rounds in the randomized LOCAL model, but the only known upper bound is the trivial brute-force solution of O(n) rounds. Locally optimal cut in constant-degree graphs is perhaps the simplest example of a locally checkable labeling problem for which there is still such a large gap between current upper and lower bounds.
We show that in constant-degree graphs, all local potential problems, including locally optimal cut, can be solved in logO(1) n rounds, both in the deterministic and randomized LOCAL models. In particular, the deterministic round complexity of the locally optimal cut problem is now settled to log螛(1) n.
Our algorithms also apply to the general case of graphs of maximum degree 螖. For the special case of locally optimal cut, we obtain a deterministic algorithm that runs in 螖2 脮(濒辞驳6 n). Furthermore, we show that a dependence in 螖 is necessary: we prove a lower bound of 惟(min{螖,鈭歯}) rounds; in particular, there is no polylogarithmic-round algorithm for the general case.
- Slides
(National University of Singapore)
Byzantine Agreement with Predictions
Sparsification Framework for Directed Densest Subgraph in MPC, Semi-Streaming, and Sublinear-Time Model
-
Directed densest subgraph is a classical primitive for finding dense directed structure in large graphs, with applications ranging from web graph analysis to fraud detection, data mining, and computational biology. In this talk, I will discuss a sparsification framework for directed densest subgraph in memory-constrained computation. Prior approaches based on uniform edge sampling and peeling each face natural barriers: uniform sampling may require 惟(n3/2) sampled edges, while peeling-based methods may require 螛(log n) iterations. The main observation is that *the first* peeling step is already quite informative: either the remaining graph is dense enough to contain a near-optimal solution, or the number of relevant edges becomes small enough that a (refined) uniform sparsification retains only 脮(n) edges. This leads to a simple Peel-Sample framework that combines one low-degree peeling step with a uniform sampling. Instantiating the framework yields improved algorithms for directed densest subgraph in semi-streaming, near-linear-memory MPC, and sublinear-time settings.
- Slides
Survey of the Distributed Lov谩sz Local Lemma
LCLs with and without knowledge of n
-
The LOCAL model, as the name suggests forces us to use only local information to solve graph problems. However, it is common to assume that nodes are given some initial global knowledge, such as an upper bound on the network size n. This is very much non-local information. Is this necessary? Can we restrict the LOCAL model to not include these global assumptions?
We investigate these questions by looking what happens for a setting in which we understand almost everything: LCLs on bounded degree trees. Specifically the so-called polynomial-regime of LCLs on trees. We show how dropping the assumption, that nodes are provided with an upper bound on n, turns the considered problems into global problems. This indicates, that we need some sort of initial knowledge on the value of n.
We further investigate what happens if a polynomial bound on n is provided to the nodes and what happens if only a bound on the size of the maximum Id is given. We identify the mechanism underlying the difficulties of these settings and provide tight results.
- Slides
Self-Stabilizing Algorithms in the Uniform Port Model
-
We introduce a distributed computational model referred to as the uniform port model. An algorithm operating in this model is defined by means of local automata associated with the ports (a.k.a. half-edges) of the input graph. The crux of the uniform port model is that the local automata are identical and admit a constant size description, making the model truly uniform. Moreover, since the new model explicitly supports the assignment of (input and) output labels to the graph's (half-)edges, it is much more expressive than existing truly uniform distributed computational models that are restricted to assignments of output labels to the graph's nodes. The main technical contribution presented in this talk is the design of efficient (i.e., with poly-logarithmic runtime) self-stabilizing uniform port algorithms for various fundamental local symmetry breaking problems, including maximal matching, maximal independent set, sinkless orientation, and maximal edge and node c-coloring. While efficient self-stabilizing algorithms for local symmetry breaking problems have been extensively studied in stronger computational models, our work is the first to demonstrate the existence of such algorithms in a truly uniform model.
- Slides
(CISPA Helmholtz Center for Information Security, Saarbr眉cken)
On Distributed Lower Bound Techniques and a Gap in the Distributed Complexity Landscape
-
In this talk, I will survey some recent developments on lower bound techniques for the LOCAL model. In particular, I will discuss a fundamental relation between the two main techniques for proving 惟(log n)-round lower bounds for locally checkable labeling (LCL) problems and possible approaches for proving decidability for the 蠅(log* n) - o(log n) gap in the complexity landscape of LCL problems.
The talk is based on joint work with Alkida Balliu, Yi-Jun Chang, Jan Greb铆k, Ole Gabsdil, Tim G枚ttlicher, Christoph Grunau, Dennis Olivetti, Vasek Rozho艌, Jukka Suomela, and Zoltan Vidny谩nszky.
- Slides
Towards Optimal-pass Semi-streaming Matchings and Beyond
-
The semi-streaming complexity of approximate maximum matching remains a central question in graph streaming. In this talk, I will present a deterministic algorithm that computes a (1+蔚)-approximate maximum matching in O(\epsilon^{-6}) semi-streaming passes, improving the previous O(蔚-19)-pass bound of Fischer, Mitrovi膰, and Uitto [STOC鈥�22]. This makes substantial progress on Open Question 2 of Assadi [SOSA鈥�24].
The main idea is to revisit the FMU framework through a more structured view of the maintained search objects. We formulate them using blossoms and represent them via alternating trees, which allows parts of the analysis to be treated in a bipartite-like manner despite working in general graphs. This leads to a simpler correctness argument and yields analogous round-complexity improvements in the MPC and CONGEST models.
This is joint work with Slobodan Mitrovi膰, Piotr Sankowski, and Wen-Horng Sheu, and appeared at ICALP 2025.
- Slides
(National University of Singapore)
Distributed Minimum Weight Cycle Approximation
-
In this talk, we present an algorithm that, for any real number k > 1.62, computes a (k+1)-approximation of the minimum-weight cycle in an undirected weighted graph in 脮(n((k+1)/(2k+1)) + D) rounds with high probability in the CONGEST model. The algorithm is based on variants of the Miller-Peng-Xu low-diameter decomposition algorithm. Our result is conditionally tight in the following sense: for any integer k 鈮� 1, finding a (k+1鈭捨�)-approximation of the minimum-weight cycle in an undirected weighted graph requires 惟虄(n((k+1)/(2k+1)) + D) rounds, assuming the Erd艖s girth conjecture.
- Slides
Graph k-Coloring in Average Sublinear Time
-
Graph k-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a k-coloring over the set of all k-colorable graphs on n vertices. A highly influential result of Dyer-Frieze from 1989 gave an algorithm with O(n2) average runtime for constant k. This quadratic runtime appeared natural (and possibly even optimal) since almost all k-colorable graphs have 螛(n2) edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Ku膷era in 1995 to average runtime O(n2/k) for every k 鈮� nc where c 鈭� (0,1). Nevertheless, in the most interesting case of k = O(1), the best-known bound remained quadratic in n. The true average complexity of the k-coloring problem has remained elusive for the last three decades.
We break the longstanding quadratic barrier. Our main result in this paper shows that the exact average-case complexity of this fundamental problem is 螛(nk) for every k 鈮� nc' and some c' 鈭� (0, 1). For k = O(1), this reveals the average sublinear nature of k-colorability: the average-case complexity is
linear in n , and thussublinear in the size of the input . We further show that our 螛(nk) average runtime isoptimal , since a simple bound proves that every algorithm that correctly k-colors all k-colorable graphs requires 惟虄(nk) average runtime.An interesting aspect of our proofs is that they rely on insights from the theory of sublinear and local algorithms. Observe that our main result above immediately implies that for an average k-colorable graph G, it takes average time O(k) to color each of the vertices of G. Our technique actually gives another result which is of independent interest: there is a local algorithm that, with all but exponentially small probability, on input G, finds the color of every given vertex in average-case probe complexity poly(k).
A key new ingredient in our approach is a method of certifying the unique colorability of random subgraphs. This certification step uses results from algorithmic graph regularity that appear to be new in the context of average-case graph coloring.
- Slides
(The Institute of Mathematical Science, Chennai, India)
Graph Coloring Problems in the Two Party Communication Model
-
We study the communication complexity of fundamental graph problems on n-vertex graphs with maximum degree 螖, where the edge set is partitioned between two players. We present communication-optimal and round-efficient protocols for (螖+1)-vertex coloring, (2螖-1)-edge coloring, and maximal independent set (MIS). Each of these problems can be solved using 螛(n) bits of total communication. Our protocols achieve round complexities of O(loglog n log 螖) for (螖+1)-vertex coloring, O(1) for (2螖-1)-edge coloring, and O(log1/2 n) for MIS. The talk will focus primarily on the coloring results. We conclude by highlighting some open problems.
- Slides
Amnesiac Flooding and Self-Healing
-
About the simplest distributed algorithm one can imagine on a network/graph is flooding: A node v in possession of a message M to be eventually sent to every node on the graph (this is called achieving broadcast) sends M to all neighbours except those who just sent M to it. To ensure termination and avoiding the network choking with congestion, v keeps a copy of M and rejects the message if M ever comes around again. But what if the nodes did not keep a copy of M, and the protocol was a single rule - 'send and forget'? We call this stateless, memoryless protocol Amnesiac Flooding (AF) (), and discover that surprisingly, not only does this algorithm terminate on every synchronous undirected graph but does so in almost optimal time [PODC2019, STACS2020, DistributedComputing2023]. Further, we recently discovered that AF is unique - under certain reasonable conditions, this is the only distributed algorithm that can achieve broadcast with termination [DISC2025].
Self-healing is a fault-tolerance paradigm which seeks to maintain certain desirable (often global) invariants in a responsive manner on reconfigurable systems/networks - a powerful adversary deletes/inserts a single node, the affected neighbours are informed and the distributed algorithm responds by adding or dropping edges. Early papers along with maintaining connectivity with low degree increase, also maintain diameter after deletions (Forgiving Tree [PODC2008]), maintain stretch with either deletion or insertion (ForgivingGraph [PODC2009]), and expansion (Xheal [PODC2011]). The self-healing model itself can be seen as a responsive variant of the P2P-CONGEST model (Dconstructor [PODC2020]). What if there are some `active鈥� processes/algorithms running when the network encounters an attack?: CompactFT [ICDCN鈥�16, ICDCN鈥�20] devised self-healing compact routing solutions for Tree topologies while introducing the Compact Local Streaming (CLS)/Compact Message Passing (CMP) model for networks of nodes with sublinear working memories.
Are there other examples of Unique algorithms in literature, and is counting the number of algorithms for solving a problem a concept we can reasonably postulate? What can be achieved in stateless, memoryless, CLS settings, and can processes such as Amnesiac Flooding be run in a self-healing network?
- Slides
Challenges in Quantum Distributed Computing
I talk about quantum distributed computing, i.e., distributed computing in which the processors in a network can exchange quantum messages. After briefly describing the history of quantum computing, I present three main techniques used to design quantum distributed algorithms demonstrating significant quantum advantages for certain distributed computing tasks: quantum symmetry breaking for zero-error leader election, quantum search in the CONGEST model, and quantum non-locality in the LOCAL model. I also discuss challenges and important open questions.
- Slides
Robust Shattering Arguments (part 1)
-
Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that large sets of distant nodes remain unresolved, often via independence assumptions justified by locality.
We show that these assumptions fail for pre-shattering procedures that run for super-constant rounds, where dependencies accumulate over time. As a result, several standard shattering arguments in the literature are incomplete, including those for maximal independent set, (螖+1)-coloring, and the distributed Lov谩sz Local Lemma (LLL).
We provide a systematic repair of these analyses. Our main contribution is a corrected shattering analysis of the Fischer-Ghaffari LLL algorithm. In addition, we develop general tools that capture common patterns in modern algorithms and yield the required decay bounds without relying on independence. We also present explicit counterexamples to commonly used shattering lemmas.
Overall, we establish a robust and reusable foundation for shattering arguments in the presence of long-range dependencies.
Robust Shattering Arguments (part 2)
-
Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that large sets of distant nodes remain unresolved, often via independence assumptions justified by locality.
We show that these assumptions fail for pre-shattering procedures that run for super-constant rounds, where dependencies accumulate over time. As a result, several standard shattering arguments in the literature are incomplete, including those for maximal independent set, (螖+1)-coloring, and the distributed Lov谩sz Local Lemma (LLL).
We provide a systematic repair of these analyses. Our main contribution is a corrected shattering analysis of the Fischer-Ghaffari LLL algorithm. In addition, we develop general tools that capture common patterns in modern algorithms and yield the required decay bounds without relying on independence. We also present explicit counterexamples to commonly used shattering lemmas.
Overall, we establish a robust and reusable foundation for shattering arguments in the presence of long-range dependencies.
- Slides
Breaking Barriers and Closing Gaps for MIS and MM by Understanding Vertex Survival Probability
-
We study the problem of finding a maximal independent set (MIS) in the standard LOCAL model of distributed computing. Classical algorithms by Luby [JACM'86] and Alon, Babai, and Itai [JALG'86] find an MIS in O(log n) rounds in n-node graphs with high probability. Despite decades of research, the existence of any o(log n)-round algorithm for general graphs remains one of the major open problems in the field. Interestingly, the hard instances for this problem must contain constant-length cycles. This is because there exists a sublogarithmic-round algorithm for graphs with super-constant girth; i.e., graphs where the length of the shortest cycle is 蠅(1), as shown by Ghaffari~[SODA'16]. Thus, resolving this 鈮�40-year-old open problem requires understanding the family of graphs that contain k-cycles for some constant k. In this work, we come very close to resolving this 鈮�40-year-old open problem by presenting a sublogarithmic-round algorithm for graphs that can contain k-cycles for all k>6. Specifically, our algorithm finds an MIS in O((log 螖) / (log(log* c)) + poly(log log n)) rounds, as long as the graph does not contain cycles of length 鈮�6, where 螖 is the maximum degree of the graph. As a result, we push the limit on the girth of graphs that admit sublogarithmic-round algorithms from k=蠅(1) all the way down to a small constant k=7. This also implies a o(sqrt(log n)) round algorithm for MIS in trees, refuting a conjecture from the book by Barenboim and Elkin.
- Slides
(Japan Advanced Institute of Science and Technology)
What Can We Learn from Neuronal Connectivity Alone?
-
Recent advances in electron microscopy and computer vision have enabled the mapping of complete wiring diagrams, called connectomes, of brain regions and even entire brains. The emergence of these increasingly large-scale datasets has intensified the need for efficient and accurate neuronal cell type identification. Traditional approaches rely on labor-intensive analyses of molecular, anatomical, and physiological features. As a step toward fully automated neuronal cell type classification, we present NTAC (Neuronal Type Assignment from Connectivity), a method for grouping neurons into cell types based solely on synaptic connectivity.
Our approach is grounded in the hypothesis that synaptic connectivity is key to determining neuronal cell types, and our results provide the strongest evidence to date supporting its validity. We further show that this connectivity-based approach extends beyond cell typing, enabling neurotransmitter classification from synaptic connectivity alone.
Neighborhood Similarity: A New Application and Technique
-
Neighborhood similarity approaches, such as almost-clique decomposition, have led to many efficient distributed and parallel algorithms for problems such as graph coloring and correlation clustering. In this talk, I will present a new result on min-max correlation clustering based on such an approach, as well as a convenient tool for computing neighborhood similarity. Finally, I will discuss some open problems related to this topic.
The talk is based on 鈥淢in-Max Correlation Clustering via Neighborhood Similarity,鈥� a joint work with Nairen Cao and Steven Roche.
- Slides
Zero-Knowledge Distributed Certification
-
Distributed certification is a set of mechanisms that allows an all-knowing prover to convince the units of a communication network that the network's state has some desired property, such as being 3-colorable or triangle-free. Classical mechanisms, such as proof labeling schemes (PLS), consist of a message from the prover to each unit, followed by one round of communication between each unit and its neighbors. Later works consider extensions, called distributed interactive proofs, in which the prover and the units can have multiple rounds of communication before the units communicate among themselves.
Recently, Bick, Kol, and Oshman (SODA '22) defined a zero-knowledge version of distributed interactive proofs, where the prover convinces the units of the network's state without revealing any other information about the network's state or structure. In follow-up work, Grilo, Paz, and Perry presented a non-interactive version of this idea, returning to PLS-style certification with the additional property of being zero-knowledge.
In this talk, I will present some interesting technical ideas from both works. I will survey the main results regarding 3-colorability and subgraph detection.
- Slides
Detailed schedule
Alphabetic list of speakers
- Sebastian Brandt
- Yi-Jun Chang
- Francesco d'Amore
- Yuval Emek
- Pierre Fraigniaud
- Seth Gilbert
- Hsin-Hao Su
- Christian Konrad
- Fran莽ois Le Gall
- Yannic Maus
- Gopinath Mishra
- Slobodan Mitrovi膰
- Anish Mukherjee
- Alexandre Nolin
- Ami Paz
- Seth Pettie
- Ronitt Rubinfeld
- Aaron Schild
- Gustav Schmid
- Gregory Schwartzman
- Amitabh Trehan
The workshop is by invitation only
Dates
May 18 - 21, 2026
Location
, Calle Giustinian, 2893, 30124 Venezia, Italy
Organizers:
- (Gran Sasso Science Institute (GSSI))
- (神马福利影片)
- (Durham University)