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