Direct Product via Round-Preserving Compression
Direct Product via Round-Preserving Compression
复制标题
通过保圆压缩直接积
DOI：
10.1007/978-3-642-39206-1_20
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
A. Yehudayoff
中科院分区：
文献类型：
--
作者：
M. Braverman;Anup Rao;Omri Weinstein;A. Yehudayoff
得到了两方有界轮通信复杂度的一个强直积定理。设sucr（μ,f，C）表示当(x,y) μ时，在计算f（x,y）时最多使用C位通信的r轮通信协议的最大成功概率。Jain等人最近表明，如果${\sf suc}_{r}(\mu,f,C) \leq \frac{2}{3}$和$T\ll (C-\Omega (r^2)) \cdot\frac{n}{r}$，那么${\sf suc}_r(\mu^n,f^n,T)\leq \exp(-\Omega(n/r^2))$。这里我们证明，如果${\sf suc}_{7r}(\mu,f,C) \leq \frac{2}{3}$和T≪（C−Ω（r logr））·n，那么${\sf suc}_{r}(\mu^n,f^n,T)\leq\exp(-\Omega(n))$。直到一个对数因子，我们的结果渐近地匹配由平凡解给出的su7r （μn,fn，T）的上界，该解对每个坐标独立地应用每拷贝最优协议。该证明依赖于一种压缩方案，该方案比已知的压缩方案改善了轮数和通信复杂性之间的权衡。
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.