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$ Commented Feb 19, 2015 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$ Commented Feb 19, 2015 at 10:35

1 Answer 1


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$ Commented Feb 19, 2015 at 8:21

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.