ECCC-Report TR13-035https://eccc.weizmann.ac.il/report/2013/035Comments and Revisions published for TR13-035en-usFri, 08 Mar 2013 16:13:30 +0200
Revision 1
| Direct product via round-preserving compression |
Mark Braverman,
Anup Rao,
Omri Weinstein,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2013/035#revision1We 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.Fri, 08 Mar 2013 16:13:30 +0200https://eccc.weizmann.ac.il/report/2013/035#revision1
Paper TR13-035
| Direct product via round-preserving compression |
Mark Braverman,
Anup Rao,
Omri Weinstein,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2013/035We 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.Thu, 07 Mar 2013 01:06:12 +0200https://eccc.weizmann.ac.il/report/2013/035