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