A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity
A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity
复制标题
两方有界轮公币通信复杂性的直积定理
DOI：
10.1007/s00453-015-0100-0
复制
发表时间：
2012
期刊：
影响因子：
1.1
通讯作者：
Penghui Yao
中科院分区：
文献类型：
--
作者：
Rahul Jain;A. Pereszlényi;Penghui Yao
在给定的计算模型中，一个问题的强直积定理指出，为了计算问题的k个实例，如果我们提供的资源小于计算问题的一个实例所需资源的k倍，并且成功概率恒定，则正确计算所有k个实例的概率在k中呈指数小。本文研究了两方有界轮公钥随机通信复杂度模型。我们证明了在这个模型中的任何完整的关系的通信复杂性的直积定理。特别地，我们的结果暗示了所有完全关系的两方常数轮公共硬币随机通信复杂度的强直积定理。作为结果的直接应用，我们得到了指针追逐问题的一个强直积定理。这个问题已经被很好地研究，以理解在经典和量子通信协议中的轮v/s通信权衡。我们的结果推广了Jain的结果，Jain的结果可以看作是消息数为1时的特殊情况。我们的结果可以被认为是解决两方公共硬币通信复杂性的强直积猜想的重要进展，这是该领域的一个主要开放问题。我们使用信息理论的参数显示我们的结果。我们的论点和技术建立在耆那教使用的基础上。在我们的工作中使用的一个关键工具，也是由Jain是一个消息压缩技术，由于布雷弗曼和饶，谁用它来显示一个直和定理在同一模型的通信复杂性，我们认为。另一个重要的工具，我们使用的是一个相关的采样协议，例如，已被用于Holenstein证明一个并行重复定理的两个证明游戏。
A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any complete relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-round public-coin randomized communication complexity of all complete relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain which can be regarded as the special case when the number of messages is one. Our result can be considered as an important progress towards settling the strong direct product conjecture for two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used by Jain. One key tool used in our work and also by Jain is a message compression technique due to Braverman and Rao, who used it to show a direct sum theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol which, for example, has been used by Holenstein for proving a parallel repetition theorem for two-prover games.