ECCC-Report TR12-143https://eccc.weizmann.ac.il/report/2012/143Comments and Revisions published for TR12-143en-usTue, 02 Apr 2013 22:30:11 +0300
Revision 2
| Direct Products in Communication Complexity |
Anup Rao,
Amir Yehudayoff,
Mark Braverman,
Omri Weinstein
https://eccc.weizmann.ac.il/report/2012/143#revision2We 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))$.Tue, 02 Apr 2013 22:30:11 +0300https://eccc.weizmann.ac.il/report/2012/143#revision2
Revision 1
| Direct Products in Communication Complexity |
Anup Rao,
Amir Yehudayoff,
Mark Braverman,
Omri Weinstein
https://eccc.weizmann.ac.il/report/2012/143#revision1We 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))$.Fri, 23 Nov 2012 02:16:02 +0200https://eccc.weizmann.ac.il/report/2012/143#revision1
Paper TR12-143
| Direct Products in Communication Complexity |
Anup Rao,
Amir Yehudayoff,
Mark Braverman,
Omri Weinstein
https://eccc.weizmann.ac.il/report/2012/143We 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)).Mon, 05 Nov 2012 23:40:25 +0200https://eccc.weizmann.ac.il/report/2012/143