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

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

event speaker icon
אמיר יהודיוף (טכניון
event date icon
יום רביעי, 08.05.2013, 12:30
event location icon
טאוב 201
Communication complexity deals with the amount of communication between parties needed to achieve a common goal. It was introduced by Yao and has found numerous applications since. We shall discuss a direct product theorem for 2-party communication. That is, for example, if at least C bits of communication is needed to compute a function f with probability at least 2/3, then communicating much less than roughly C n^{1/2} bits to compute n copies of f yields exponentially small success probability.

Based on work with Mark Braverman, Anup Rao and Omri Weinstein.ts.