Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR12-143 | 2nd April 2013 22:30

Direct Products in Communication Complexity

RSS-Feed




Revision #2
Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
Accepted on: 2nd April 2013 22:30
Downloads: 1364
Keywords: 


Abstract:

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



Changes to previous version:

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 to TR12-143 | 23rd November 2012 02:16

Direct Products in Communication Complexity





Revision #1
Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
Accepted on: 23rd November 2012 02:16
Downloads: 972
Keywords: 


Abstract:

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



Changes to previous version:

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.


Paper:

TR12-143 | 5th November 2012 23:40

Direct Products in Communication Complexity





TR12-143
Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
Publication: 5th November 2012 23:40
Downloads: 1286
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint