Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
复制标题
通过零通信协议和应用程序降低信息复杂性
DOI：
10.1109/focs.2012.68
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
David Xiao
中科院分区：
文献类型：
--
作者：
Iordanis Kerenidis;Sophie Laplante;Virginie Lerays;J. Roland;David Xiao
我们发现，几乎所有已知的通信复杂性的下界方法也是信息复杂性的下界。特别是，我们定义了一个放松的版本的分区界的Jain和Klauck，并证明它下界的任何功能的信息复杂性。我们的宽松划分界限包括所有基于范数的方法（例如γ2方法）和基于矩形的方法（例如矩形/损坏界限，平滑矩形界限和差异界限），除了划分界限。我们的结果使用矩形和零通信协议之间的新连接，其中玩家可以输出值或中止。我们证明了下面的压缩引理：给定一个协议的函数f与信息复杂度I，可以构建一个零通信协议，具有非中止概率至少2-O（I），并计算正确的f与高概率条件下不中止。然后，我们展示了这样一个零通信协议与放松的分区界限。我们利用我们的主要定理解决了Braver提出的三个悬而未决的问题：首先，我们证明了子空间矢量问题的信息复杂度为O（n1/3），这反过来意味着量子通信复杂度和经典信息复杂度之间存在指数分离。此外，我们还给出了差距汉明距离问题的信息复杂度的一个O（n）下界.
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I) and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.