Lower bounds for Nondeterministic Multiparty Communication 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.
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&lt;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.