Stronger Lower Bounds on Nondeterministic Multiparty Communication This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication.

From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty communication in the number-on-the-forehead model (see the paper by Lee and Shraibman). The problem is 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.

Edit(dec/8/2010): I have two more questions,

2) Corruption (cf. Lee and Shraibman 2007, section 4.5) is used for lower bounding 2-sided error randomized communication. Is there any extension of corruption to nondeterminism? A nondeterministic protocol accepts with probability strictly greater than 0, and rejects with probability 1.

3) Is there any other lower bound based on information-theoretic arguments?
There is a tight (within an additive log n) lower bound method for nondeterministic multiparty communication complexity:

Put a hard distribution on the 1-inputs, and measure the size of the largest 1-monochromatic cylinder intersection. To see that it's tight take the relevant section in Kushilevitz and Nisan, and replace the word 'rectangle' with 'cylinder intersection'.

The corruption bound, or rather the one-sided version of it (where you prove that all large rectangles contain a constant fraction of 0-inputs) is harder to use and yields stronger results, for instance allows you to prove MA-communication complexity lower bounds.