1 citations · 1 across the 7 of their papers we have counts for
8 papers
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…
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 t…
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],…
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 number…
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 that…
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-spar…
Faster All-Pairs Optimal Electric Car Routing
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2
We present a randomized -time algorithm for computing \emph{optimal energetic paths} for an electric car between all pairs of vertices in an -vertex directed…
Search Trees on Trees via LP
Yaniv Sadeh, Haim Kaplan, Uri Zwick
We consider the problem of computing optimal search trees on trees (STTs). STTs generalize binary search trees (BSTs) in which we search nodes in a path (linear order) to search tr…