论文标题
通信复杂性的近乎最佳的直接和定理
A near-optimal direct-sum theorem for communication complexity
论文作者
论文摘要
我们为两方随机通信复杂性显示了几乎最佳的直接和定理。令$ f \ subseteq x \ times y \ times z $成为一个关系，$ \ varepsilon> 0 $，$ k $是整数。我们显示，$$ \ MATHRM {R}^{\ MATHRM {pub}} _ \ VAREPSILON（f^k）\ cdot \ log（\ Mathrm {r}^{\ Mathrm {\ Mathrm {pub}} _ \ varepsilon（f varepsilon（f^k）） \ Mathrm {r}^{\ Mathrm {pub}} _ \ varepsilon（f））\ enspace，$$，其中$ f^k = f \ times \ ldots \ ldots \ times f $（$ k $ -times）和$ \ \ \ m}代表公共coin随机通信复杂性，具有最差的错误错误$ \ varepsilon $。给定$ f^k $的协议$ \ MATHCAL {p} $，带有通信费用$ C \ CDOT K $和WORST-CASE错误$ \ VAREPSILON $，我们展示了一个协议$ \ MATHCAL {Q} $ for $ f $ for $ f $ for $ f $ for for External-forment-cost $ o（c）$（c）$和worst-erst-erst-ers-error $ \ varepsilon $。然后，我们使用Barak，Braverman，Chen和Rao [2013]引起的消息压缩协议，以使用通信$ O（C \ CDOT \ log（C \ CDOT K））模拟$ \ Mathcal {q} $以达到我们的结果。为了显示这种减少，我们显示了一些新的链条，以实现容量，这是通信渠道可以传输的最大信息。我们在游戏理论中使用了NASH平衡的强大概念及其在适当定义的游戏中的存在，以达到链条以供产能。这些链条具有独立的兴趣。
We show a near optimal direct-sum theorem for the two-party randomized communication complexity. Let $f\subseteq X \times Y\times Z$ be a relation, $\varepsilon> 0$ and $k$ be an integer. We show, $$\mathrm{R}^{\mathrm{pub}}_\varepsilon(f^k) \cdot \log(\mathrm{R}^{\mathrm{pub}}_\varepsilon(f^k)) \ge Ω(k \cdot \mathrm{R}^{\mathrm{pub}}_\varepsilon(f)) \enspace,$$ where $f^k= f \times \ldots \times f$ ($k$-times) and $\mathrm{R}^{\mathrm{pub}}_\varepsilon(\cdot)$ represents the public-coin randomized communication complexity with worst-case error $\varepsilon$. Given a protocol $\mathcal{P}$ for $f^k$ with communication cost $c \cdot k$ and worst-case error $\varepsilon$, we exhibit a protocol $\mathcal{Q}$ for $f$ with external-information-cost $O(c)$ and worst-error $\varepsilon$. We then use a message compression protocol due to Barak, Braverman, Chen and Rao [2013] for simulating $\mathcal{Q}$ with communication $O(c \cdot \log(c\cdot k))$ to arrive at our result. To show this reduction we show some new chain-rules for capacity, the maximum information that can be transmitted by a communication channel. We use the powerful concept of Nash-Equilibrium in game-theory, and its existence in suitably defined games, to arrive at the chain-rules for capacity. These chain-rules are of independent interest.
