The Taub Faculty of Computer Science Events and Talks

We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of fooling views and exemplify its strength by proving two new lower bounds for triangle membership in the CONGEST(B) model: (i) Any 11-round algorithm requires B≥cΔlogn for a constant c>0c. (ii) If B=1, even in constant-degree graphs any algorithm must take Ω(log∗n) rounds. The implication of the former is the first proven separation between the LOCAL and the CONGEST models for deterministic triangle membership. The latter result is the first non-trivial lower bound on the number of rounds required, even for {triangle detection}, under limited bandwidth. All previous known techniques are provably incapable of giving these bounds. We hope that our approach may pave the way for proving lower bounds for additional problems in various settings of distributed computing for which previous techniques do not suffice.

This is a joint work with Amir Abboud, Keren Censor-Hillel, and Christoph Lenzen.