Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Multiparty Communication Complexity of Disjointness

Revision #3
Accepted on: 25th February 2008 00:00
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
Accepted on: 23rd January 2008 00:00
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
Accepted on: 22nd January 2008 00:00
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
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)}.