Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Direct Products in Communication Complexity
event speaker icon
Amir Yehudayoff (Technion)
event date icon
Wednesday, 08.05.2013, 12:30
event location icon
Taub 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.