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

אירועים

Theory Seminar: Direct Products in Communication Complexity
event speaker icon
אמיר יהודיוף (טכניון
event date icon
יום רביעי, 8.5.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.
[בחזרה לאינדקס האירועים]