The Taub Faculty of Computer Science Events and Talks

In this talk I will sketch two lower bound techniques for distributed models under bandwidth restrictions. The first is via reductions from the two party communication model, which is a well known technique for achieving lower bounds in distributed computing. I will show a new gadget for this framework that allows us to prove stronger lower bounds. As an example for this gadget, I will present a new lower bound for computing the exact or approximate diameter. The second technique is called the Fooling Views technique, and we use it together with extremal graph combinatorics to show a lower bound for solving triangle detection. This talk is based on joint works with Amir Abboud, Keren Censor-Hillel, Christoph Lenzen, and Ami Paz.