• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Communication With Imperfectly Shared Randomness
【24h】

Communication With Imperfectly Shared Randomness

机译：不完全共享的随机性交流

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Communication complexity investigates the amount of communication needed for two or more players to determine some joint function of their private inputs. For many interesting functions, the communication complexity can be much smaller than basic information theoretic measures associated with the players’ inputs such as the input length, the entropy, or even the conditional entropy. Communication complexity of many functions reduces further when the players share randomness. Classical works studied the communication complexity of functions when the interacting players share randomness perfectly, i.e., they get identical copies of randomness from a common source. This paper considers the variant of this question when the players share randomness imperfectly, i.e., when they get noisy copies of the randomness produced by some common source. Our main result shows that any function that can be computed by a -bit protocol in the perfect sharing model has a -bit protocol in the setting of imperfectly shared randomness and such an exponential growth is necessary. Our upper bound relies on ideas from locality sensitive hashing, while lower bounds rely on hypercontractivity and a new invariance principle tailored for communication protocols.
机译：沟通复杂性调查了两个或更多参与者确定其私人投入的某些联合功能所需的沟通量。对于许多有趣的功能，通信复杂度可能比与玩家输入相关的基本信息理论量度小得多，例如输入长度，熵甚至条件熵。当玩家共享随机性时，许多功能的通信复杂性进一步降低。古典作品研究了交互参与者完美共享随机性时功能的通信复杂性，即他们从共同的来源获得了相同的随机性副本。当参与者不完全共享随机性时，即当他们获得某个共同来源产生的随机性的嘈杂副本时，本文考虑了该问题的变体。我们的主要结果表明，在完美共享模型中，可以由-bit协议计算的任何函数在不完全共享随机性的设置中都具有-bit协议，并且这种指数增长是必要的。我们的上限依赖于局部敏感哈希的思想，而下限则依赖于超伸缩性和针对通信协议量身定制的新不变性原理。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号