Theory Seminar: Direct Products in Communication Complexity

Amir Yehudayoff (Technion)
Wednesday, 8.5.2013, 12:30
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.

Back to the index of events