<p>There is a tight (within an additive log n) lower bound method for nondeterministic multiparty communication complexity:</p>

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

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

CC BY-SA 2.5
2010-12-27T08:14:15.253Z
thanks for the answer, that's what I was looking for. Do you have any references on the one-sided version of corruption?
Marcos Villagra
CC BY-SA 2.5
2011-01-03T05:26:52.043Z
The corruption bound as such was introduced by Yao "Lower Bounds by Probabilistic Arguments", FOCS 83. It was used in the paper mentioned above, but also most famously by Razborov in his paper about the randomized complexity of Disjointness (the previous linear lower bound by Kalyanasundaram and Schnitger does not seem to use the corruption method). This is really the one-sided version of corruption: Razborov (and before him Babai et al.) show that all 0-rectangles are small or have large error (which is untrue for 1-rectangles).
Hartmut Klauck
CC BY-SA 2.5
2011-01-03T05:28:47.130Z
The corruption method didn't really get a name until the paper "A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness." by Beame at al. in CCC 05. The method is studied in its relation to MA-communication in Klauck: "Rectangle Size Bounds and Threshold Covers in Communication Complexity", CCC 03. A much better formulation as a linear program is in Jain and Klauck: "The Partition Bound for Classical Communication Complexity and Query Complexity", CCC '10.
Hartmut Klauck
CC BY-SA 2.5
2010-12-24T14:23:46.203Z
2010-12-24T14:23:46.203Z
Hartmut Klauck
<p>This is a continuation of my previous question on <a href="https://cstheory.stackexchange.com/questions/3517/lower-bounds-for-nondeterministic-multiparty-communication">Lower bounds for Nondeterministic Multiparty Communication</a>.</p>

<p>From the <a href="https://cstheory.stackexchange.com/questions/3517/lower-bounds-for-nondeterministic-multiparty-communication/3613#3613">answer</a>, the $\mu^\infty$ norm lower bounds nondeterministic multiparty communication in the number-on-the-forehead model (see the paper by <a href="http://www.eccc.uni-trier.de/report/2008/003/" rel="nofollow noreferrer">Lee and Shraibman</a>). 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.</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.</p>

<p><strong>Edit(dec/8/2010):</strong> I have two more questions,</p>

<p>2) Corruption (cf. <a href="http://www.research.rutgers.edu/~troyjlee/survey_plain.pdf" rel="nofollow noreferrer">Lee and Shraibman 2007</a>, 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.</p>

<p>3) Is there any other lower bound based on information-theoretic arguments?</p>

<cc.complexity-theory><lower-bounds><communication-complexity><norms>
Stronger Lower Bounds on Nondeterministic Multiparty Communication
Marcos Villagra
# Stronger Lower Bounds on Nondeterministic Multiparty Communication

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

This is a continuation of my previous question on [Lower bounds for Nondeterministic Multiparty Communication](https://cstheory.stackexchange.com/questions/3517/lower-bounds-for-nondeterministic-multiparty-communication).

From the [answer](https://cstheory.stackexchange.com/questions/3517/lower-bounds-for-nondeterministic-multiparty-communication/3613#3613), the $\mu^\infty$ norm lower bounds nondeterministic multiparty communication in the number-on-the-forehead model (see the paper by [Lee and Shraibman](http://www.eccc.uni-trier.de/report/2008/003/)). 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](http://www.research.rutgers.edu/~troyjlee/survey_plain.pdf), 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?

**Tags:** cc.complexity-theory, lower-bounds, communication-complexity, norms

---

## 1 answers

### Answer by username_1 on 2010-12-24. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: thanks for the answer, that's what I was looking for. Do you have any references on the one-sided version of corruption?  
> **username_1**: The corruption bound as such was introduced by Yao "Lower Bounds by Probabilistic Arguments", FOCS 83. It was used in the paper mentioned above, but also most famously by Razborov in his paper about the randomized complexity of Disjointness (the previous linear lower bound by Kalyanasundaram and Schnitger does not seem to use the corruption method). This is really the one-sided version of corruption: Razborov (and before him Babai et al.) show that all 0-rectangles are small or have large error (which is untrue for 1-rectangles).  
> **username_1**: The corruption method didn't really get a name until the paper "A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness." by Beame at al. in CCC 05. The method is studied in its relation to MA-communication in Klauck: "Rectangle Size Bounds and Threshold Covers in Communication Complexity", CCC 03. A much better formulation as a linear program is in Jain and Klauck: "The Partition Bound for Classical Communication Complexity and Query Complexity", CCC '10.  

---

