We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let $suc(mu,f,C)$ denote the maximum success probability of a 2-party communication protocol for computing $f(x,y)$ with $C$ bits of communication, when the inputs $(x,y)$ are drawn from the distribution $mu$. Let $mu^n$ be the product distribution on $n$ inputs and $f^n$ denote the function that computes $n$ copies of $f$ on these inputs.

We prove that if $T log^{1.5} T < Cn$ and $suc(mu,f,C)<0.9$, then $suc(mu^n,f^n,T) < \exp(-\Omega(n))$. When $mu$ is a product distribution, we prove a nearly optimal result: as long as $T log^2 T < Cn$, we must have $suc(mu^n,f^n,T) < exp(\Omega(n))$.

We fixed an inconsistency in the paper regarding the definition of computation of a function in communication complexity. We also added a discussion regarding a counterexample for a direct product like statement.

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let $\mathsf{suc}(\mu, f, C)$ denote the maximum success probability of a 2-party communication protocol for computing $f(x,y)$ with $C$ bits of communication, when the inputs $(x,y)$ are drawn from the distribution $\mu$. Let $\mu^n$ be the product distribution on $n$ inputs and $f^n$ denote the function that computes $n$ copies of $f$ on these inputs.

We prove that if $T \log^{3/2} T \ll C \sqrt{n}$ and $\mathsf{suc}(\mu,f,C) < \frac{2}{3}$, then $\mathsf{suc}(\mu^n,f^n,T) \leq \exp(-\Omega(n))$. When $\mu$ is a product distribution, we prove a nearly optimal result: as long as $T \log^2 T \ll Cn$, we must have $\mathsf{suc}(\mu^n, f^n,T) \leq \exp(-\Omega(n))$.

In this revision we update section 3 of the paper in order to correct
an error in the earlier version (last equations of Claims 25 and 27)
that was discovered by Penghui Yao. We deeply thank him for that.
Our revision affects all of section 3.

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(?,f,C) denote the maximum success probability of a 2-party communication protocol for computing f(x,y) with C bits of communication, when the inputs (x,y) are drawn from the distribution ?. Let ?^n be the product distribution on n inputs and f^n denote the function that computes n copies of f on these inputs.

We prove that if T log^1.5 T ? Cn and suc(?,f,C)<0.9, then suc(?n,fn,T)?exp(??(n)). When ? is a product distribution, we prove a nearly optimal result: as long as T log^2 T ? Cn, we must have suc(?n,fn,T) ? exp(??(n)).