Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks

Amir Abboud, Keren Censor-Hillel, Seri Khoury

We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Speci…