8 papers
Dynamic Edge Coloring of Forests
Haim Kaplan, David Naori, Yaniv Sadeh
In the \emph{dynamic edge coloring} problem, one has to maintain a graph of maximum degree with at most colors, under edge updates. A prominent objective is to minimize…
An Efficient Private Algorithm for Community Detection
Vincent Cohen-Addad, Alessandro Epasto, Haim Kaplan +2
In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exac…
Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
Yaniv Sadeh, Haim Kaplan
We study the maintenance of a -edge-coloring () in a fully dynamic graph with maximum degree . We focus on minimizing \emph{recourse} which equals the numbe…
A Simpler Analysis for -Clairvoyant Flow Time Scheduling
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We simplify the proof of the optimality of the Shortest Lower-Bound First (SLF) algorithm, introduced by Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai [FOCS'25],…
Improved Tree Sparsifiers in Near-Linear Time
Daniel Agassy, Dani Dorfman, Haim Kaplan
A \emph{tree cut-sparsifier} of quality of a graph is a single tree that preserves the capacities of all cuts in the graph up to a factor of . A \emph{tree flow-sp…
Expander Decomposition for Non-Uniform Vertex Measures
Daniel Agassy, Dani Dorfman, Haim Kaplan
A -expander-decomposition of a graph (with vertices and edges) is a partition of into clusters with conductance , such…