Multiparty Communication Complexity of Disjointness

Simple item page
dc.creatorChattopadhyay, Arkadev
dc.creatorAda, Anil
dc.date2008-01-23
dc.date2008-02-20
dc.date.accessioned2026-07-07T09:21:39Z
dc.date.available2026-07-07T09:21:39Z
dc.descriptionWe 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.
dc.description15 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/0801.3624
dc.identifierhttp://arxiv.org/abs/0801.3624
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155102
dc.subjectComputational Complexity
dc.titleMultiparty Communication Complexity of Disjointness
dc.typetext

Files

Collections

arXiv