期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2017
卷号：2017
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A basic goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems f : ( 0 1 n ) k 0 1 with k log n parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every k log n , showing in both cases that (1 + log n log 1 + k log n ) bits are necessary and sufficient. In particular, these problems admit constant-cost protocols if and only if the number of parties is k n for some constant 0."> 0
关键词：inner product mod 2 ; multiparty communication complexity ; Number-On-Forehead model ; Set disjointness problem
