This is a continuation of my previous question on communication lower bounds for partial boolean functions.

Can someone suggest any reference on lower bounds for nondeterministic multiparty communication? I've been surveying the papers in the field, but everybody seems to show separations of the following type: a lower bound for randomized protocol and an (smaller) upper bound for a nondeterministic protocol. See for example, David, Pitassi, and Viola 2009, Gavinsky and Sherstov 2010, Beame, David, Pitassi, and Woelfel 2010.

Specifically, I would like to know if there exists a norm (e.g. $\gamma_k$ for $k$ parties) that lower bounds nondeterministic multiparty communication in either the number-in-the-forehead or number-in-hand model.

  • $\begingroup$ should I put the edit part as an answer and make a different question? $\endgroup$ Dec 7, 2010 at 5:28
  • $\begingroup$ You should put the new result you found in an answer. (maybe you'll get a self-learner badge!) As for the new problem, it is fine to leave it in the same question. $\endgroup$ Dec 7, 2010 at 5:33
  • $\begingroup$ I think it's fine to add it as an answer. you asked the question some time ago, and waited for answers. You then found one - that's exactly what the self-learner badge is for $\endgroup$ Dec 7, 2010 at 6:08

1 Answer 1


After much reading, I've found the following paper

Troy Lee and Adi Shraibman. Disjointment is hard in the multi-party number-on-the-forehead model. In Proceedings of IEEE 23rd Annual Conference on Computational Complexity. June 22-26 2008.

The authors show that bounded error randomized communication is lower bounded by an approximate cylinder intersection norm $\mu_\alpha$ (cf. definition 5 in the paper).

Theorem 6: Let M be a sign $k$-tensor, and $0\leq \epsilon<1/2$. Then $R_\epsilon^k(M)\geq \log(\mu^\alpha(M))-\log(\alpha_\epsilon)$ where $\alpha_\epsilon=1/(1-2\epsilon)$ and $\alpha\geq\alpha_\epsilon$.

Then, they make the following remark.

Remark 7: It is nice to note that since a non-deterministic protocol induces a covering of the tensor with cylinder intersections, it follows that $\log\mu^\infty$ is a lower bound on non-deterministic communication complexity.

This answers my question. The problem now is when $\alpha\to\infty$ the authors show that for any given sign matrix $M$, $\mu^\infty(M)=1/Disc(M)$, where $Disc(M)$ is the discrepancy of $M$. It is a problem because the best lower bounds we can prove using discrepancy are polylogarithmic in the size of the input. For example, for disjointment with $k$ parties the lower bound is $\Omega(\log n/(k-1))$. In the same piece of work, the authors show that for randomized protocols, disjointment requires $\Omega(\frac{n^{1/(k+1)}}{2^{2^k}})$ using the $\mu^\alpha$ norm.

Is there any other norm stronger than discrepancy that can be used for lower bounds in nondeterministic multiparty communication? Or is it tight? These results are very recent, so maybe this is an open problem. The follow-up to this question is here.

  • $\begingroup$ you can accept your own answer :). also, maybe you can ask the new question separately ? $\endgroup$ Dec 7, 2010 at 6:33
  • $\begingroup$ done. The new question is now in cstheory.stackexchange.com/questions/3614/… $\endgroup$ Dec 7, 2010 at 6:52
  • $\begingroup$ just before accepting it, I would like to wait and see if someone knows any other lower bound, e.g. information theoretic bound $\endgroup$ Dec 7, 2010 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.