92 citations · 120 across the 20 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DC2017
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…
cs.DS2017★ 13 cited
A -Approximation for Maximum Weight Matching in the Semi-Streaming Model
Ami Paz, Gregory Schwartzman
We present a simple deterministic single-pass -approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently…