1 citations · 1 across the 7 of their papers we have counts for
9 papers
Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity
Antoine El-Hayek, Monika Henzinger, Da Wei Zheng
Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot of atten…
Ranking Opinions with Few States in Population Protocols
Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek +1
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) int…
Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
Antoine El-Hayek, Monika Henzinger, Jason Li
We present an exact fully-dynamic minimum cut algorithm that runs in deterministic update time when the minimum cut size is at most for any ,…
An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model
Antoine El-Hayek, Robert Elsässer, Stefan Schmid
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…
Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
Antoine El-Hayek, Monika Henzinger, Jason Li
Dynamically maintaining the minimum cut in a graph under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound…
On -Matching and Fully-Dynamic Maximum -Edge Coloring
Antoine El-Hayek, Kathrin Hanauer, Monika Henzinger
Given a graph that is modified by a sequence of edge insertions and deletions, we study the Maximum -Edge Coloring problem Having access to colors, how can we color as m…
Time Complexity of Broadcast and Consensus for Randomized Oblivious Message Adversaries
Antoine El-Hayek, Monika Henzinger, Stefan Schmid
Broadcast and consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network lin…
Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear
Antoine El-Hayek, Monika Henzinger, Stefan Schmid
We study the broadcast problem on dynamic networks with processes. The processes communicate in synchronous rounds along an arbitrary rooted tree. The sequence of trees is give…
Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
Antoine El-Hayek, Monika Henzinger, Stefan Schmid
Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting …