Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR13-035 | 8th March 2013 16:13

#### Direct product via round-preserving compression

Revision #1
Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
Accepted on: 8th March 2013 16:13
Downloads: 2405
Keywords:

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

TR13-035
Authors: Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff
Publication: 7th March 2013 01:06
Downloads: 2601
Keywords:

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