<p>After much reading, I've found the following paper</p>

<p>Troy Lee and Adi Shraibman. <a href="https://cstheory.stackexchange.com/questions/3614/stronger-lower-bounds-on-nondeterministic-multiparty-communication">Disjointment is hard in the multi-party number-on-the-forehead model</a>. In <em>Proceedings of IEEE 23rd Annual Conference on Computational Complexity</em>. June 22-26 2008.</p>

<p>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).</p>

<blockquote>
  <p><strong>Theorem 6:</strong> 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$.</p>
</blockquote>

<p>Then, they make the following remark.</p>

<blockquote>
  <p><strong>Remark 7:</strong> 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.</p>
</blockquote>

<p>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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/3614/stronger-lower-bounds-on-nondeterministic-multiparty-communication">here</a>.</p>

CC BY-SA 2.5
2010-12-07T06:33:39.047Z
you can accept your own answer :). also, maybe you can ask the new question separately ?
Suresh Venkat
CC BY-SA 2.5
2010-12-07T06:52:20.107Z
done. The new question is now in http://cstheory.stackexchange.com/questions/3614/stronger-lower-bounds-on-nondeterministic-multiparty-communication
Marcos Villagra
CC BY-SA 2.5
2010-12-07T08:21:17.130Z
just before accepting it, I would like to wait and see if someone knows any other lower bound, e.g. information theoretic bound
Marcos Villagra
CC BY-SA 2.5
2010-12-07T06:30:07.007Z
2010-12-07T22:44:48.773Z
2017-04-13T12:32:28.077Z
Marcos Villagra
<p>This is a continuation of my previous question on <a href="https://cstheory.stackexchange.com/questions/3349/communication-lower-bounds-for-partial-boolean-functions">communication lower bounds for partial boolean functions</a>.</p>

<p>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, <a href="http://portal.acm.org/citation.cfm?id=1595391.1595392" rel="nofollow noreferrer">David, Pitassi, and Viola 2009</a>, <a href="http://theoryofcomputing.org/articles/v006a010/" rel="nofollow noreferrer">Gavinsky and Sherstov 2010</a>, <a href="http://theoryofcomputing.org/articles/v006a009/" rel="nofollow noreferrer">Beame, David, Pitassi, and Woelfel 2010</a>.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-07T05:28:34.580Z
should I put the edit part as an answer and make a different question?
Marcos Villagra
CC BY-SA 2.5
2010-12-07T05:33:17.367Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-07T06:08:39.210Z
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
Suresh Venkat
<cc.complexity-theory><reference-request><lower-bounds><communication-complexity><norms>
Lower bounds for Nondeterministic Multiparty Communication
Marcos Villagra
# Lower bounds for Nondeterministic Multiparty Communication

(Asked by: username_0 on 2010-12-04)

This is a continuation of my previous question on [communication lower bounds for partial boolean functions](https://cstheory.stackexchange.com/questions/3349/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](http://portal.acm.org/citation.cfm?id=1595391.1595392), [Gavinsky and Sherstov 2010](http://theoryofcomputing.org/articles/v006a010/), [Beame, David, Pitassi, and Woelfel 2010](http://theoryofcomputing.org/articles/v006a009/).

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.

**Tags:** cc.complexity-theory, reference-request, lower-bounds, communication-complexity, norms
> **Comments:**
> **username_0**: should I put the edit part as an answer and make a different question?  
> **username_1**: 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.  
> **username_2**: 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  

---

## 1 answers

### Answer by username_0 on 2010-12-07. Score: 4 | Accepted answer

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](https://cstheory.stackexchange.com/questions/3614/stronger-lower-bounds-on-nondeterministic-multiparty-communication). 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](https://cstheory.stackexchange.com/questions/3614/stronger-lower-bounds-on-nondeterministic-multiparty-communication).

> **Comments:**
> **username_2**: you can accept your own answer :). also, maybe you can ask the new question separately ?  
> **username_0**: done. The new question is now in http://cstheory.stackexchange.com/questions/3614/stronger-lower-bounds-on-nondeterministic-multiparty-communication  
> **username_0**: just before accepting it, I would like to wait and see if someone knows any other lower bound, e.g. information theoretic bound  

---

