7
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ thanks for the answer, that's what I was looking for. Do you have any references on the one-sided version of corruption? $\endgroup$
    – Marcos Villagra
    Commented Dec 27, 2010 at 8:14
  • $\begingroup$ 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). $\endgroup$
    – Hartmut Klauck
    Commented Jan 3, 2011 at 5:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hartmut Klauck
    Commented Jan 3, 2011 at 5:28

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.