Direct products in communication complexity.
Omri Weinstein
April 2, 2014

We prove exponentially small upper bounds on the success probability for computing multiple independent copies of any function over any distribution using a communication protocol. If C bits of communication are required for solving a single copy of f(x,y) over input distribution \mu with probability 2/3, then any protocol attempting to solve n independent copies of f using << \sqrt{n}*C communication, will succeed with probability only exp(-Omega(n)). If \mu is a product distribution, we prove a near optimal result: Any protocol using << n*C communication in order to solve all copies will succeed with probability at most exp(-Omega(n)). This matches the communication and success of the trivial sequential protocol.

Joint work with Mark Braverman, Anup Rao and Amir Yehudayoff.