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.