92 citations · 170 across the 35 of their papers we have counts for
7 papers · 1 filter
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion
Amir Abboud, Keren Censor-Hillel, Seri Khoury +1
We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of \emph{fooling views} and exemplify its strength by…
Fast Distributed Approximation for TAP and 2-Edge-Connectivity
Keren Censor-Hillel, Michal Dory
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph and a spanning tree for it, and the goal is to augment with a…
Distributed Approximation of Maximum Independent Set and Maximum Matching
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari +1
We present a simple distributed -approximation algorithm for maximum weight independent set (MaxIS) in the model which completes in $O(\texttt{MIS}(G)\cdot \l…
Fast Distributed Approximation for Max-Cut
Keren Censor-Hillel, Rina Levy, Hadas Shachnai
Finding a maximum cut is a fundamental task in many computational settings. Surprisingly, it has been insufficiently studied in the classic distributed settings, where vertices com…
Broadcasting in Noisy Radio Networks
Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz +1
The widely-studied radio network model [Chlamtac and Kutten, 1985] is a graph-based description that captures the inherent impact of collisions in wireless communication. In this m…
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
Keren Censor-Hillel, Seri Khoury, Ami Paz
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact comput…
Making Asynchronous Distributed Computations Robust to Noise
Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interac…