首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:The Communication Complexity of Number-In-Hand Set Disjointness with No Promise
  • 本地全文:下载
  • 作者:Mark Braverman ; Rotem Oshman
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Set disjointness is one of the most fundamental problems in communication complexity. In the multi-party number-in-hand version of set disjointness, k players receive private inputs X 1 X k 1 n , and their goal is to determine whether or not k i =1 X i = . In this paper we prove a tight lower bound on the randomized communication complexity of multi-party number-in-hand set disjointness in the shared blackboard model. Our main tool is information complexity. Intuitively, in order to "become convinced" that their sets are disjoint, the players must discover, for each element j [ n ] , some player i such that j X i ; this information is worth n log k bits. We are able to formalize this information and show that the players must learn a total of ( n log k ) bits of information about each other's inputs, and this implies a communication lower bound of ( n log k ) as well. Overall, we obtain the tight bound ( n log k + k ) on the problem, and give a simple matching deterministic upper bound.

国家哲学社会科学文献中心版权所有