• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Communication Complexity:From Two-Party to Multiparty
【24h】

Communication Complexity:From Two-Party to Multiparty

机译：沟通复杂度：从两方到多方

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

摘要

We consider the multiparty communication complexity model, where k players holding inputs x1,...,.xk communicate to compute the value f(x1,..., xk) of a function f known to all of them. Yao's classic two-party communication complexity model [3] is the special case k = 2 (see also [2]). In the first part of the talk, we survey some basic results regarding the two-party model, emphasizing methods for proving lower-bounds. In the second part of the talk, we consider the case where there are at least three parties (k ≥ 3). The main lower bound technique for the communication complexity of such multiparty problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. We discuss the power of partition arguments for both deterministic and randomized protocols. (This part is based on a joint work with Jan Draisma and Enav Weinreb [1].)
机译：我们考虑多方通信复杂性模型，其中k个持有输入x1，...，。xk的参与者进行通信以计算所有人都知道的函数f的值f（x1，...，xk）。姚的经典的两方通信复杂度模型[3]是特殊情况k = 2（另请参见[2]）。在演讲的第一部分，我们调查了有关两方模型的一些基本结果，重点介绍了证明下界的方法。在演讲的第二部分，我们考虑至少有三个参与方（k≥3）的情况。解决此类多方问题的通信复杂性的主要下限技术是分区参数：将k个参与者分成两个不相交的参与者集，并为诱发的两方通信复杂性问题找到下限。我们讨论了确定性和随机协议的分区参数的功能。 （本部分基于与Jan Draisma和Enav Weinreb [1]的联合工作。）

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号