Exponential Separation of Information and Communication for Boolean Functions
Exponential Separation of Information and Communication for Boolean Functions
复制标题
布尔函数的信息和通信的指数分离
DOI：
10.1145/2746539.2746572
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ran Raz
中科院分区：
文献类型：
--
作者：
Anat Ganor;Gillat Kol;Ran Raz
通过给出一个信息复杂度≤ O（k）且分布通信复杂度≥ 2k的部分函数的例子，证明了布尔函数的通信复杂度与信息复杂度之间存在指数差距.这表明部分布尔函数的通信协议不能总是压缩到其内部信息。根据Braverman [Bra12]的结果，我们的差距是最大的可能。根据Braverman和Rao [BR 11]的结果，我们的示例显示了通信复杂度和摊销通信复杂度之间的差距，这意味着布尔函数的分布式通信复杂度的严格直接和结果不能成立，从而回答了一个长期存在的悬而未决的问题。我们的技术建立在[GKR 14]的基础上，该技术证明了具有非常长输出的关系的类似结果（k的双指数长）。除了更强的结果，目前的工作给出了一个更简单的证明，受益于布尔函数的输出长度短。另一个（概念）的贡献，我们的工作是相对差异的方法，一个新的基于矩形的方法证明布尔函数的通信复杂性下界，强大到足以分离信息的复杂性和通信的复杂性。
We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol for a partial boolean function cannot always be compressed to its internal information. By a result of Braverman [Bra12], our gap is the largest possible. By a result of Braverman and Rao [BR11], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity of boolean functions cannot hold, answering a long standing open problem. Our techniques build on [GKR14], that proved a similar result for relations with very long outputs (double exponentially long in k). In addition to the stronger result, the current work gives a simpler proof, benefiting from the short output length of boolean functions. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.