Inspired by the questions Nondeterministic communication complexity of set disjointness?, I was wondering about the following:

Is there an example of a function $f$ where the nondeterministic communication complexity $N(f)$ is asymptotically smaller than the deterministic communication complexity $D(f)$.

When $f$ is the Equality problem or the Set Disjointness problem, we seem to have $D(f) = N(f)$ and, as far as I can tell, the common techniques for showing lower bounds for deterministic protocols (fooling sets and the rank method) work just as well for nondeterministic protocols.

Are there any known techniques that yield stronger lower bounds for deterministic protocols compared to nondeterministic protocols?

  • $\begingroup$ I don't think rank gives lower bounds for non-deterministic protocols. For example the negation of the equality function corresponds to a full rank matrix but has a non-deterministic protocol with $\log n$ bits. $\endgroup$ Feb 19 '15 at 8:55
  • $\begingroup$ See Kushilevitz/Nisan Example 2.12: this shows that the $k$-disjointness function (where Alice and Bob each receive a $k$-element subset of $[n]$ and have to determine if they are disjoint) achieves a quadratic gap when $k = \log n$. $\endgroup$ Feb 19 '15 at 10:35

It seems to me that there is some incoherency in the question. What do you mean by better? Are you looking for a function where $N(f) \ll D(f)$ or a function where $D(f) \ll N(f)$?

Deterministic protocols are a special case of nondeterministic protocols, so we always have $N(f) \leq D(f)$.

For examples of functions where $N(f) \ll D(f)$ have a look at the Nisan and Kushilevitz's book.

  • $\begingroup$ Apologies, I updated the question. $\endgroup$ Feb 19 '15 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.