92 citations · 170 across the 35 of their papers we have counts for
5 papers · 1 filter
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
Keren Censor-Hillel, Merav Parter, Gregory Schwartzman
This paper addresses the cornerstone family of \emph{local problems} in distributed computing, and investigates the curious gap between randomized and deterministic solutions under…
Distributed Construction of Purely Additive Spanners
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz +1
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases.…
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, Keren Censor-Hillel, Seri Khoury
We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Speci…
A Distributed -Approximation for Vertex Cover in Rounds
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman
We present a simple deterministic distributed -approximation algorithm for minimum weight vertex cover, which completes in rounds, where is the max…
Fast Distributed Algorithms for Testing Graph Properties
Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman +1
We initiate a thorough study of \emph{distributed property testing} -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular,…