Revision #3 Authors: Arkadev Chattopadhyay, Anil Ada

Accepted on: 25th February 2008 00:00

Downloads: 3773

Keywords:

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 Authors: Arkadev Chattopadhyay, Anil Ada

Accepted on: 23rd January 2008 00:00

Downloads: 2095

Keywords:

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 Authors: Arkadev Chattopadhyay, Anil Ada

Accepted on: 22nd January 2008 00:00

Downloads: 2161

Keywords:

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.

TR08-002 Authors: Arkadev Chattopadhyay, Anil Ada

Publication: 15th January 2008 11:09

Downloads: 2283

Keywords:

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.