5th Workshop Complexity and Algorithms (CoA 2026)

[important: change of location due to room unavailability: 1 place de l'école, next to the Monod ENS campus, see below]

Local Information

The 5th annual workshop of the working group Complexity and Algorithms (gt-CoA) will take place on October 5–7, 2026, in Lyon, at the Descartes site of ENS de Lyon, Amphitheater D2. The program will begin after lunch on Monday and will end before lunch on Wednesday.
Participants are responsible for booking their accommodation in Lyon.

The organizers thank Alantha Newman, Laure Savetier, and Marie Bozo for their great help in preparing the event.

Registration

Registration is free but mandatory (link below). The registration deadline is September 18th.

Invited Talks

Lélia Blin (Memory Minimization in Self-Stabilization)

Abstract: Self-stabilization is a fundamental property of distributed systems that enables them to recover a correct state after transient faults, without requiring external intervention. Even if the global state of the system becomes corrupted, a self-stabilizing protocol guarantees convergence to a legitimate configuration from which its behavior satisfies the intended specification. A central challenge in this area is achieving memory efficiency, since reducing the information stored and exchanged by nodes lowers communication overhead and enables more resource-efficient fault-tolerant systems. The notion of silent algorithms, where nodes eventually stop changing state, plays an important role in the theory of self-stabilization. However, silent algorithms impose constraints on the memory size. For example, Ω(log n) bits per node are required for tasks such as leader election or spanning tree construction. However, being silent is not inherently required for designing self-stabilizing algorithms. By relaxing this constraint, one can design protocols that drastically reduce space complexity. In this talk, we will discuss the issue of space complexity of self-stabilizing algorithms. We will present recent advances in the design of memory-efficient self-stabilizing algorithms for fundamental distributed tasks.

Arnaud Labourel (Can Like Attract Like? A Study of Homonymous Gathering in Networks)

Abstract: In this talk, I consider the problem of gathering a team of mobile agents in a network. The objective is for all agents to meet at the same node and simultaneously declare that gathering has been achieved. In contrast with most previous work, where agents have distinct identifiers that allow them to break symmetries deterministically, we allow several agents to share the same label, leading to situations of homonymy. In this setting, the possibility of gathering in all graphs depends on the composition of the team, that is, on the multiset of agent labels. I will present a complete characterization of gatherable teams, together with a polynomial-time gathering algorithm for all such teams. The algorithm requires only o(log log log μ) bits of initial information, where μ denotes the maximum multiplicity of a label in the team. As a corollary, this yields the first polynomial-time gathering algorithm for agents with distinct labels that does not rely on any shared prior knowledge.

This talk is based on joint work with Stéphane Devismes and Yoann Dieudonné, accepted at STOC 2026.

Tutorials

Lianna Hambardzumyan (From Arithmetic Progressions to Algorithms and Lower Bounds)

Abstract: The breakthrough work of Kelley and Meka (2023) on sets free of 3-term arithmetic progressions has sparked a wave of progress on classical problems concerning additive patterns in dense sets, including the recent breakthrough of Jaber, Liu, Lovett, Ostuni, and Sawhney on the corners problem. In this talk, I will give a high-level overview of the ideas behind these developments, emphasizing the structure-versus-randomness philosophy and the modern density-increment techniques that make the new bounds possible. I will also discuss how these advances extend beyond additive combinatorics, including applications to multiparty communication complexity and related algorithmic problems such as combinatorial Boolean matrix multiplication. The goal of the talk is to illustrate how progress on fundamental questions about additive patterns can lead to new insights across theoretical computer science.

Nguyễn Kim Thắng (Multiplicative Weight Update through the Lens of Algorithm Design and Machine Learning)

Abstract: The Multiplicative Weights Update (MWU) method is a powerful and versatile framework in algorithm design, particularly in the study of online algorithms. Interestingly, this method has independently emerged in several areas of computer science and optimization, often under different names and formulations.

In this talk, we will present the MWU method from two complementary perspectives: online algorithms and machine learning, with a particular focus on online optimization. We will highlight the connections between these viewpoints and show how translating ideas across domains can lead to flexible and effective approaches. In particular, we will illustrate how techniques from online optimization can be used to solve problems in online algorithms, and conversely, how insights from online algorithms can inform online optimization methods.

Call for Presentations

We invite people working in, or close to, the field of Algorithms and Complexity to submit a talk proposal on a topic of their choice (via the registration form). Contributed talks are 20-minute long including questions.