Exponential separation of communication and external information
Exponential separation of communication and external information
复制标题
通信和外部信息呈指数分离
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Raz
中科院分区：
文献类型：
--
作者：
Anat Ganor;Gillat Kol;R. Raz
通过分析布雷弗曼提出的候选通信任务，我们发现通信复杂性和外部信息复杂性之间存在指数级差距。在此之前，人们只知道通信复杂性和内部信息复杂性的分离。更精确地说，我们得到了一个搜索问题的显式例子，对于任何输入分布，外部信息复杂度≤ O（k），对于某些输入分布，分布通信复杂度≥ 2k。特别地，这表明通信协议不能总是被压缩到其外部信息。由于布雷弗曼的结果，我们的差距是最大的可能。此外，由于O（k）的上界的外部信息复杂性的问题是相对于任何输入分布，我们的结果意味着一个指数差距之间的通信复杂性和信息复杂性（内部和外部）在非分布设置的布雷弗曼。在这种情况下，即使是内部信息复杂度，以前也没有发现差距。
We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman. Previously, only a separation of communication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity ≤ O(k), with respect to any input distribution, and distributional communication complexity ≥ 2k, with respect to some input distribution. In particular, this shows that a communication protocol cannot always be compressed to its external information. By a result of Braverman, our gap is the largest possible. Moreover, since the upper bound of O(k) on the external information complexity of the problem is obtained with respect to any input distribution, our result implies an exponential gap between communication complexity and information complexity (both internal and external) in the non-distributional setting of Braverman. In this setting, no gap was previously known, even for internal information complexity.