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

Accepted on: 8th March 2013 16:13

Downloads: 2868

Keywords:

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.

TR13-035 Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Publication: 7th March 2013 01:06

Downloads: 3007

Keywords:

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.