Computer Science – Computational Complexity
Scientific paper
2008-01-23
Computer Science
Computational Complexity
15 pages, 2 figures
Scientific paper
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.
Ada Anil
Chattopadhyay Arkadev
No associations
LandOfFree
Multiparty Communication Complexity of Disjointness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multiparty Communication Complexity of Disjointness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiparty Communication Complexity of Disjointness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-183956