Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR08-002 | 25th February 2008 00:00

Multiparty Communication Complexity of Disjointness

RSS-Feed




Revision #3
Authors: Arkadev Chattopadhyay, Anil Ada
Accepted on: 25th February 2008 00:00
Downloads: 5490
Keywords: 


Abstract:

We obtain a lower bound of $\Omega\bigg(\frac{n^{\frac{1}{k+1}}}{2^{2^k}
(k-1)2^{k-1}}\bigg)$ on the $k$-party randomized communication complexity of the Disjointness function in the `Number on the Forehead' model of multiparty communication. In particular, this yields a bound of
$n^{\Omega(1)}$ when $k$ is a constant. 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(\log \log 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 Lov\'{a}sz-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 obatin 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.


Revision #2 to TR08-002 | 23rd January 2008 00:00

Multiparty Communication Complexity of Disjointness





Revision #2
Authors: Arkadev Chattopadhyay, Anil Ada
Accepted on: 23rd January 2008 00:00
Downloads: 2967
Keywords: 


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(\log \log 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(\log \log 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 Lov\'{a}sz-Schrijver proofs.

To obtain our result, we further develop the ``Generalized Discrepancy Method" recently suggested by Sherstov \cite{She07b}. The other main components of the proof are the ``Approximation/Orthogonality Principle" that also appears in \cite{She07b} and techniques to estimate discrepancy under non-uniform distribution developed by Chattopadhyay \cite{Cha07}.

A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.


Revision #1 to TR08-002 | 22nd January 2008 00:00

Multiparty Communication Complexity of Disjointness





Revision #1
Authors: Arkadev Chattopadhyay, Anil Ada
Accepted on: 22nd January 2008 00:00
Downloads: 2990
Keywords: 


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(\log \log 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(\log \log 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 Lov\'{a}sz-Schrijver proofs.

To obtain our result, we further develop the ``Generalized Discrepancy Method" recently suggested by Sherstov \cite{She07b}. The other main components of the proof are the ``Approximation/Orthogonality Principle" that also appears in \cite{She07b} and techniques to estimate discrepancy under non-uniform distribution developed by Chattopadhyay \cite{Cha07}.

A similar bound for Disjointness has been recently and independently obtained by Lee and Shraibman.


Paper:

TR08-002 | 19th December 2007 00:00

Multiparty Communication Complexity of Disjointness





TR08-002
Authors: Arkadev Chattopadhyay, Anil Ada
Publication: 15th January 2008 11:09
Downloads: 3131
Keywords: 


Abstract:

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method yields strong bounds for functions induced by a symmetric predicate if the approximation degree of the predicate is n^{\Omega(1)}.
Similar bounds have been independently obtained recently by Lee and Shraibman.



ISSN 1433-8092 | Imprint