The Taub Faculty of Computer Science Events and Talks
Seri Khoury (M.Sc. Thesis Seminar)
Monday, 25.06.2018, 13:30
Advisor: Prof. Keren Censor-Hillel
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.