• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Exponential Separation of Information and Communication
【24h】

Exponential Separation of Information and Communication

机译：信息与通信的指数分离

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：通过给出通信任务（关系）的显式示例，信息复杂度≤O（k），分布通信复杂度≥2k，我们展示了通信复杂度和信息复杂度之间的指数差距。这表明通信协议不能始终被压缩为其内部信息。通过Braverman [1]的结果，我们的差距是最大的。通过Braverman和Rao [2]的结果，我们的示例显示了通信复杂度与摊销的通信复杂度之间的差距，这意味着无法满足分布式通信复杂度的紧迫直接和结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号