2 papers
cs.DS2019★ 2 cited
Hardness of Distributed Optimization
Nir Bachrach, Keren Censor-Hillel, Michal Dory +3
This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing $\t…
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…