92 citations · 170 across the 35 of their papers we have counts for
4 papers · 2 filters
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…
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…
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…