215 citations · 792 across the 83 of their papers we have counts for
115 papers
Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts
David A. Bader, Adil Chhabra, Ernestine Großmann +3
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last y…
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…
Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
Monika Henzinger, Jason Li, Satish Rao +1
In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time which he termed near-linear time meaning linear (…
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…
Differential Privacy for Clustering Under Continual Observation
Max Dupré la Tour, Monika Henzinger, David Saulpic
We consider the problem of clustering privately a dataset in that undergoes both insertion and deletion of points. Specifically, we give an -differentia…
A Unifying Framework for Differentially Private Sums under Continual Observation
Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay
We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for…