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 #1 to TR13-035 | 8th March 2013 16:13

Direct product via round-preserving compression

RSS-Feed

Abstract:

We obtain a strong direct product theorem for two-party bounded round communication complexity.
Let $\suc_r(\mu,f,C)$ denote the maximum success probability of an $r$-round communication protocol that uses
at most $C$ bits of communication in computing $f(x,y)$ when $(x,y)\sim \mu$.
Jain et al. \cite{JainPP12} have recently showed that if
$\suc_{r}(\mu,f,C) \leq \frac{2}{3}$ and
$T\ll (C-\Omega (r^2)) \cdot\frac{n}{r}$, then $\suc_r(\mu^n,f^n,T)\leq \exp(-\Omega(n/r^2))$.
Here we prove that
if $\suc_{7r}(\mu,f,C) \leq \frac{2}{3}$ and $T \ll (C- \Omega(r \log r)) \cdot n$ then
$\suc_{r}(\mu^n,f^n,T)\leq\exp(-\Omega(n))$.
Up to a $\log r$ factor, our result asymptotically matches the upper bound on $\suc_{7r}(\mu^n,f^n,T)$ given by the trivial solution which applies the per-copy optimal
protocol independently to each coordinate.
The proof relies on a compression scheme
that improves the tradeoff between the number of rounds and the communication complexity over known compression schemes.


Paper:

TR13-035 | 6th March 2013 04:07

Direct product via round-preserving compression


Abstract:

We obtain a strong direct product theorem for two-party bounded round communication complexity.
Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses
at most C bits of communication in computing f(x,y) when (x,y)~\mu.
Jain et al. [JPY12] have recently showed that if
suc_r(\mu,f,C) < 2/3 and T<< (C-\Omega (r^2))\cdot(n/r),
then suc_r(\mu^n,f^n,T)< exp(-\Omega(n/r^2)).
Here we prove that
if suc_{7r}(\mu,f,C) < 2/3 and T << (C- \Omega(r log r))\cdot n , then
suc_r(\mu^n,f^n,T)<exp(-\Omega(n))$.
Up to a \log(r) factor, our result asymptotically matches the upper bound on suc_{7r}(\mu^n,f^n,T) given by the trivial solution which applies the per-copy optimal protocol independently to each coordinate.
The proof relies on a compression scheme
that improves the tradeoff between the number of rounds and the communication complexity over known compression schemes.



ISSN 1433-8092 | Imprint