Name
Abstract | ||
|---|---|---|
We obtain a strong direct product theorem for two-party bounded round communication complexity. Let sucr(μ,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)~μ. Jain et al. [12] have recently showed that if ${\sf suc}_{r}(\mu,f,C) \leq \frac{2}{3}$ and $T\ll (C-\Omega (r^2)) \cdot\frac{n}{r}$, then ${\sf suc}_r(\mu^n,f^n,T)\leq \exp(-\Omega(n/r^2))$. Here we prove that if ${\sf suc}_{7r}(\mu,f,C) \leq \frac{2}{3}$ and T≪(C−Ω(r logr)) ·n then ${\sf suc}_{r}(\mu^n,f^n,T)\leq\exp(-\Omega(n))$. Up to a logr factor, our result asymptotically matches the upper bound on suc7r(μn,fn,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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-39206-1_20 | ICALP |
Keywords | DocType | Volume |
sf suc,maximum success probability,c bit,r-round communication protocol,direct product,result asymptotically,logr factor,per-copy optimal protocol,round-preserving compression,two-party bounded round communication,communication complexity,compression scheme | Journal | 20 |
ISSN | Citations | PageRank |
0302-9743 | 11 | 0.81 |
References | Authors | |
22 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Braverman | 1 | 810 | 61.60 |
| Anup Rao | 2 | 581 | 32.80 |
| omri weinstein | 3 | 49 | 6.47 |
| Amir Yehudayoff | 4 | 530 | 43.83 |