@inproceedings{22327,
  abstract     = {Population protocols are a model of distributed computing where
𝑛 agents, each a simple finite-state machine, interact in pairs to
solve a common task against a (adversarial) interaction scheduler.
This model was intensively studied in recent years; in particular,
the problem of relative majority received much attention: Each
agent starts with an input opinion (or color) out of 𝑘 possibilities,
and the goal is for each agent to eventually output the color with
the largest support in the population. Before our work, the state
complexity (the minimum number of states required per agent) was
only known to be between Ω(𝑘
2
) and𝑂(𝑘
7
). Our main contribution
is a population protocol that solves the relative majority problem
with 𝑘
3
states. We achieve this result with a new protocol called
Circles. While prior approaches in the literature relied on duels of
agents to find the majority color — an approach that proved effective
for the case with two colors — Circles partitions the agents into
circular linked lists of decreasing sizes, with the property that no
two agents with the same initial color lie in the same circle. We
show that Circles always correctly computes the desired structure
against the most adversarial of schedulers (weakly fair). We then
show that a trivial extension of Circles solves the relative majority
problem. We extend our protocol to handle various tie-breaking
mechanisms or to support the case where the agents do not share a
prior ordering of the colors. Finally, we show that a modification of
Circles solves the ranking problem with 2 · 𝑘^4
states, where each
agent must output the rank of its initial color in the population.},
  author       = {Breitkopf, Tom-Lukas and Dallot, Julien and El-Hayek, Antoine and Schmid, Stefan},
  booktitle    = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400725128},
  location     = {Egham, United Kingdom},
  pages        = {414 -- 424},
  publisher    = {Association for Computing Machinery},
  title        = {{Ranking opinions with few states in population protocols}},
  doi          = {10.1145/3796701.3815913},
  year         = {2026},
}

@phdthesis{22281,
  abstract     = {In this thesis, we took a look at networks, and more specifically, at networks that change over time, whether those are networks in the distributed algorithms sense of the word, or the graph algorithm sense. 

In distributed algorithms, we looked at two main problems. First, the broadcast problem: given n agents, each agent is tasked to forward a (unique) message to every other agent. Agents collaborate and can copy and forward all messages they have received up until that point. Broadcast is achieved when one agent has successfully broadcast its message to everyone else. We studied the case where the communication network is controlled by an adversary, under the condition that the graph is rooted in every round of communication. We show that the adversary can delay broadcast for at most  l
(1 + √
2)n
m
 rounds, improving on the $O(n\log\log n)$ previous upper bound~\cite{fugger2020radius}, and asymptotically matching the $\sim 1.5n$ lower bound~\cite{schwarz2017linear}.

We then looked at the stochastic version of the problem: here, the adversary -- parametrized by $k$ where $k=0$ signifies that the adversary has no control,  and $k=n$ that the adversary has full control -- can choose parts of the graph, and the graph is then completed stochastically. Here, we are able to look at a stronger version of broadcast: instead of having $n$ messages trying to be broadcast in parallel, we can assume that only one message needs to be broadcasted. We show the bound $\Theta(k+\log n)$.

Then, we looked at undecided states dynamics in population protocols: given a population of $n$ agents, where each initially holds an opinion among $k$ different ones. In each round, two agents are chosen uniformly at random, and can interact. If they have different opinions, they forget their opinions and become undecided. If one of them is undecided while the other has an opinion, they undecided agent copies they opinion of the decided one. The question is then, how many interactions does it take for the whole population to share the same opinion? We show a $\Omega(kn\log \frac {\sqrt n} {k \log n})$ lower bound  for any $k = o\left(\frac {\sqrt n}{\log n}\right)$.
This is tight for any $ k \le n^{\frac 1 2 - \epsilon}$, where $\epsilon >0$ can be any small constant, matching the known $O(kn\log n)$ upper bound for $k = O\left(\frac {\sqrt n} {\log ^2 n}\right)$~\cite{DBLP:conf/podc/AmirABBHKL23}.

Finally, in dynamic algorithms, we study the minimum cut problem: we are given a graph, whose vertex set we want to partition into two subsets such that the number of edges crossing from one subset to the other is minimized. Then, the graph can be updated via edge insertions or deletions, and we must update the solution without recomputing everything from scratch. We present an exact fully-dynamic minimum cut algorithm that runs in $n^{o(1)}$ deterministic update time when the minimum cut size is at most $2^{\Theta(\log^{3/4-c}n)}$ for any $c>0$, improving on the previous algorithm~\cite{DBLP:conf/soda/JinST24} whose minimum cut size limit is $(\log n)^{o(1)}$. Using sparsification and randomization techniques, we are able to extend this to all values of the minimum cut in weighted graphs, at the cost of a $(1+o(1))$-approximation ratio.},
  author       = {El-Hayek, Antoine},
  issn         = {2663-337X},
  pages        = {244},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks}},
  doi          = {10.15479/AT-ISTA-22281},
  year         = {2026},
}

@inproceedings{21720,
  abstract     = {We present an exact fully-dynamic minimum cut algorithm that runs in 𝑛𝑜⁡(1) deterministic update time when the minimum cut size is at most 2Θ⁡(log3/4−𝑐⁡𝑛) for any 𝑐 >0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (log⁡𝑛)𝑜⁡(1). Combined with graph sparsification, we obtain the first (1 +𝜖)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any 𝜖 ≥2−Θ⁡(log3/4−𝑐⁡𝑛), in 𝑛𝑜⁡(1) randomized update time.
Our main technical contribution is a deterministic local minimum cut algorithm, which replaces the randomized LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025).},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Li, Jason},
  booktitle    = {Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms},
  issn         = {1557-9468},
  location     = {Vancouver, Canada},
  pages        = {613--663},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time}},
  doi          = {10.1137/1.9781611978971.25},
  volume       = {2026},
  year         = {2026},
}

@inproceedings{19858,
  abstract     = {Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. 
We present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant.
Using these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor.},
  author       = {El-Hayek, Antoine and Hanauer, Kathrin and Henzinger, Monika H},
  booktitle    = {4th Symposium on Algorithmic Foundations of Dynamic Networks},
  isbn         = {9783959773683},
  issn         = {1868-8969},
  location     = {Liverpool, United Kingdom},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{On b-matching and fully-dynamic maximum k-edge coloring}},
  doi          = {10.4230/LIPIcs.SAND.2025.4},
  volume       = {330},
  year         = {2025},
}

@inproceedings{20052,
  abstract     = {This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in [k], the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned.
We present the Circles protocol that solves the relative majority problem with k3 states. It is always-correct under weakly fair scheduling. Not only does it improve upon the best known upper bound of O(k7), but it also shows a strikingly simpler design inspired by energy minimization in chemical settings.},
  author       = {Breitkopf, Tom-Lukas and Dallot, Julien and El-Hayek, Antoine and Schmid, Stefan},
  booktitle    = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400718854},
  location     = {Huatulco, Mexico},
  pages        = {549--552},
  publisher    = {Association for Computing Machinery},
  title        = {{Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols}},
  doi          = {10.1145/3732772.3733512},
  year         = {2025},
}

@inproceedings{20051,
  abstract     = {We revisit the majority problem in the population protocol communication model, as first studied by Angluin et al. (Distributed Computing 2008). We consider a more general version of this problem known as plurality consensus, which has already been studied intensively in the literature. In this problem, each node in a system of n nodes, has initially one of k different opinions, and they need to agree on the (relative) majority opinion. In particular, we consider the important and intensively studied model of Undecided State Dynamics.
Our main contribution is an almost tight lower bound on the stabilization time: we prove that there exists an initial configuration, even with bias \Delta = \omega(\sqrt{n\log n}), where stabilization requires \Omega(kn\log \frac {\sqrt n} {k \log n}) interactions, or equivalently, \Omega(k\log \frac {\sqrt n} {k \log n}) parallel time for any k = o\left(\frac {\sqrt n}{\log n}\right). This bound is tight for any k \le n^{\frac 1 2 - \epsilon}, where \epsilon >0 can be any small constant, as Amir et al.~(PODC'23) gave a O(k\log n) parallel time upper bound for k = O\left(\frac {\sqrt n} {\log ^2 n}\right).},
  author       = {El-Hayek, Antoine and Elsässer, Robert and Schmid, Stefan},
  booktitle    = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  isbn         = { 9798400718854},
  location     = {Huatulco, Mexico},
  publisher    = {Association for Computing Machinery},
  title        = {{An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model}},
  doi          = {10.1145/3732772.3733505},
  year         = {2025},
}

@inproceedings{19982,
  abstract     = {Dynamically maintaining the minimum cut in a graph G under edge insertions and deletion is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an n-node graph the best known (1 + o (1))-approximate algorithm takes  update time [14]. If the minimum cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n o (1) update time exists [8].
We present the first fully dynamic algorithm for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs.},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Li, Jason},
  booktitle    = {Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms},
  location     = {New Orleans, LA, United States},
  pages        = {750--784},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Fully dynamic approximate minimum cut in subpolynomial time per operation}},
  doi          = {10.1137/1.9781611978322.22},
  year         = {2025},
}

@inproceedings{18557,
  abstract     = {Broadcast and Consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Over the last years, researchers have derived several impossibility results and high time complexity lower bounds for these tasks. Specifically for the setting where in each round of communication the adversary is allowed to choose one rooted tree along which the information is disseminated, there is a lower as well as an upper bound that is linear in the number n of nodes for Broadcast and for n ≥ 3 the adversary can guarantee that Consensus never happens. This setting is called the oblivious message adversary for rooted trees. Also note that if the adversary is allowed to choose a graph that does not contain a rooted tree, then it can guarantee that Broadcast and Consensus will never happen. However, such deterministic adversarial models may be overly pessimistic, as many processes in real-world settings are stochastic in nature rather than worst-case. This paper studies Broadcast on stochastic dynamic networks and shows that the situation is very different to the deterministic case. In particular, we show that if information dissemination occurs along random rooted trees and directed Erdős–Rényi graphs, Broadcast completes in O(log n) rounds of communication with high probability. The fundamental insight in our analysis is that key variables are mutually independent. We then study two adversarial models, (a) one with Byzantine nodes and (b) one where an adversary controls the edges. (a) Our techniques without Byzantine nodes are general enough so that they can be extended to Byzantine nodes. (b) In the spirit of smoothed analysis, we introduce the notion of randomized oblivious message adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi graph) is chosen uniformly at random among the set of all such graphs that include these edges. We show that Broadcast completes in a finite number of rounds, which is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All Broadcast, and Consensus, and give lower bounds that show that most of our upper bounds are tight.},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan},
  booktitle    = {38th International Symposium on Distributed Computing},
  isbn         = {9783959773522},
  issn         = {1868-8969},
  location     = {Madrid, Spain},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges}},
  doi          = {10.4230/LIPIcs.DISC.2024.21},
  volume       = {319},
  year         = {2024},
}

@inproceedings{22373,
  abstract     = {Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. 
In the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.
We extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.
Finally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem.
For the two latter problems no upper or lower bounds were previously known.},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan},
  booktitle    = {14th Innovations in Theoretical Computer Science Conference},
  editor       = {Tauman Kalai, Yael},
  isbn         = {9783959772631},
  issn         = {1868-8969},
  keywords     = {broadcast, cover, k-broadcast, dynamic radius, dynamic graphs, oblivious message adversary, time complexity, Theory of computation → Distributed algorithms, Networks → Network algorithms},
  location     = {Cambridge, Massachusetts, USA},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks}},
  doi          = {10.4230/LIPICS.ITCS.2023.47},
  volume       = {251},
  year         = {2023},
}

@inproceedings{22374,
  abstract     = {We study the broadcast problem on dynamic networks with n processes. The processes communicate in synchronous rounds along an arbitrary rooted tree. The sequence of trees is given by an adversary whose goal is to maximize the number of rounds until at least one process reaches all other processes. Previous research has shown a ⌈(3n-1)/(2)⌉-2 lower bound and an O(n log log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1 + √2) n-1⌉ ~2.4n. Our result follows from a detailed analysis of the evolution of the adjacency matrix of the network over time.},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan},
  booktitle    = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  isbn         = {9781450392624},
  location     = {Salerno, Italy},
  pages        = {54--56},
  publisher    = {Association for Computing Machinery},
  title        = {{Brief announcement: Broadcasting time in dynamic rooted trees is linear}},
  doi          = {10.1145/3519270.3538460},
  year         = {2022},
}