Exponential Separation of Information and Communication
Exponential Separation of Information and Communication
复制标题
信息和通信的指数分离
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Raz
中科院分区：
文献类型：
--
作者：
Anat Ganor;Gillat Kol;R. Raz
我们通过给出一个通信任务（关系）的显式示例，表明通信复杂度和信息复杂度之间存在指数差距，其中信息复杂度≤ O（k），并且分布式通信复杂度≥2k。这表明通信协议不能总是被压缩到其内部信息。根据Braverman [1]的结果，我们的差距是最大的可能。通过Braverman和Rao [2]的结果，我们的例子显示了通信复杂度和分摊通信复杂度之间的差距，这意味着分布式通信复杂度的紧直和结果不能成立。
We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.