Revision #2 Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Accepted on: 2nd April 2013 22:30

Downloads: 2722

Keywords:

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.

Revision #1 Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Accepted on: 23rd November 2012 02:16

Downloads: 2230

Keywords:

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.

TR12-143 Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Publication: 5th November 2012 23:40

Downloads: 2706

Keywords:

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)).