7 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…