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

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
סרי חורי (הרצאה סמינריונית למגיסטר)
event date icon
יום שני, 25.06.2018, 13:30
event location icon
Taub 601
event speaker icon
מנחה: 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.