首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:The Power of Super-logarithmic Number of Players
  • 本地全文:下载
  • 作者:Arkadev Chattopadhyay ; Michael Saks
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a km boolean matrix A (where k is the number of players) and Player i sees all bits except those in the i-th row, and the players communicate by broadcast in order to evaluate a specified function f at A. We discover new computational power when k exceeds logm. We give a protocol with communication cost poly-logarithmic in m, for block composed functions with limited block size. These are functions of the form fg where f is a symmetric b-variate function, and g is a kr-variate function and fg(A) is defined, for a kbr matrix to be f(g(A1)g(Ab)) where Ai is the i-th kr block of A. Our protocol works provided that 1+ \ln b + 2^r">k1+lnb+2r. Ada et.al (ICALP'12) previously obtained \emph{simultaneous} and deterministic efficient protocols for composed functions of block-width r=1. The new protocol is the first to work for block composed functions with 1">r1. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction.

  • 关键词:Number-On-Forehead Protocol
国家哲学社会科学文献中心版权所有