Multiparty Communication Complexity of Disjointness

Abstract

We obtain a lower bound of n^Omega(1) on the k-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication when k is a constant. For k=o(loglog n), the bounds remain super-polylogarithmic i.e. (log n)^omega(1). The previous best lower bound for three players until recently was Omega(log n). Our bound separates the communication complexity classes NP^{CC}_k and BPP^{CC}_k for k=o(loglog n). Furthermore, by the results of Beame, Pitassi and Segerlind \cite{BPS07}, our bound implies proof size lower bounds for tree-like, degree k-1 threshold systems and superpolynomial size lower bounds for Lovasz-Schrijver proofs. Sherstov \cite{She07b} recently developed a novel technique to obtain lower bounds on two-party communication using the approximate polynomial degree of boolean functions. We obtain our results by extending his technique to the multi-party setting using ideas from Chattopadhyay \cite{Cha07}. A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.

15 pages, 2 figures

References in corpus (2)

• Quantum communication complexity of symmetric predicates
• Disjointness is hard in the multi-party number on the forehead model

Cited by in corpus (8)

• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• Communication Lower Bounds Using Dual Polynomials
• A Dual Polynomial for OR
• Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
• Separating NOF communication complexity classes RP and NP
• Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
• The Partition Bound for Classical Communication Complexity and Query Complexity
• A Strong Direct Product Theorem for Disjointness