2 citations · 5 across the 7 of their papers we have counts for
3 papers · 1 filter
Distributed Distance Approximation
Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard +2
Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can…
Distributed Weighted Min-Cut in Nearly-Optimal Time
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay +1
Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], ther…
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
Yuval Efron, Ofer Grossman, Seri Khoury
By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight resul…