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.
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.
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.
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.
