דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

New Lower Bounds for Communication Models under Bandwidth Restrictions
event speaker icon
סרי חורי, הרצאה סמינריונית למגיסטר
event date icon
יום שני, 25.6.2018, 13:30
event location icon
טאוב 601
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.
[בחזרה לאינדקס האירועים]