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

文章基本信息

  • 标题:Information Complexity for Multiparty Communication
  • 本地全文:下载
  • 作者:Diptarka Chakraborty ; Elazar Goldenberg ; Michal Koucky
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model was posed in \cite{Braverman12}. In this paper, we first give a definition of internal information cost for a protocol involving more than two parties and our definition matches the definition known for two party model. Our definition is valid for both in NIH model and NOF model. We also extend several results known for information complexity of two party model to multiparty communication setting. We show that our definition of information complexity is sub-additive in nature. We give a lower bound for the information complexity of a function involving more that two parties in terms of communication complexity and this lower bound matches with the bound known for the function evaluated by only two parties. We also show that the amortized communication complexity of a function computed by k parties is upper bounded by ( k − 1 ) times the information complexity and this relation is true for both distributional and non-distributional case.

  • 关键词:amortized complexity ; distributaional complexity ; information complexity ; Multiparty communication
国家哲学社会科学文献中心版权所有