Skip to main content Skip to navigation

Centre for Discrete Mathematics and its Applications

Abstracts and slides

Pierre Fraigniaud (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

Christian Konrad (University of Bristol)

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.

Francesco d'Amore (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 Õ(log6 n). Furthermore, we show that a dependence in Δ is necessary: we prove a lower bound of Ω(min{Δ,√n}) rounds; in particular, there is no polylogarithmic-round algorithm for the general case.

  • Slides

Seth Gilbert (National University of Singapore)

Byzantine Agreement with Predictions

Slobodan Mitrović (UC Davis)

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

Seth Pettie (University of Michigan)

Survey of the Distributed Lovász Local Lemma

Gustav Schmid (University of Freiburg)

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

Yuval Emek (Technion)

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

Sebastian Brandt (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.

Anish Mukherjee (University of Liverpool)

Towards Optimal-pass Semi-streaming Matchings and Beyond

Yi-Jun Chang (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

Ronitt Rubinfeld (MIT)

Graph k-Coloring in Average Sublinear Time

Gopinath Mishra (The Institute of Mathematical Science, Chennai, India)

Graph Coloring Problems in the Two Party Communication Model

Amitabh Trehan (Durham University)

Amnesiac Flooding and Self-Healing

François Le Gall (Nagoya University)

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

Yannic Maus (TU Graz)

Robust Shattering Arguments (part 1)

Alexandre Nolin (Télécom SudParis)

Robust Shattering Arguments (part 2)

Aaron Schild (Google Research)

Breaking Barriers and Closing Gaps for MIS and MM by Understanding Vertex Survival Probability

Gregory Schwartzman (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.

Hsin-Hao Su (Boston College)

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 “Min-Max Correlation Clustering via Neighborhood Similarity,” a joint work with Nairen Cao and Steven Roche.

Ami Paz (CNRS)

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.

Detailed schedule

Alphabetic list of speakers

The workshop is by invitation only

Dates

May 18 - 21, 2026

Location

Palazzo Giustinian Lolin, Calle Giustinian, 2893, 30124 Venezia, Italy

Organizers:

Let us know you agree to cookies

We use cookies to give you the best online experience. Please let us know if you agree to functional, advertising and performance cookies. You can update your cookie preferences at any time.

Cookie policy