The Taub Faculty of Computer Science Events and Talks

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.