New Lower Bounds for Communication Models under Bandwidth Restrictions

Seri Khoury, M.Sc. Thesis Seminar
Monday, 25.6.2018, 13:30
Taub 601
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.

Back to the index of events