<p>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)$? </p>

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

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

CC BY-SA 3.0
2015-02-19T08:21:23.153Z
Apologies, I updated the question.
MirkoMirkosovivisisic
CC BY-SA 3.0
2015-02-19T07:40:47.563Z
2015-02-19T07:40:47.563Z
Kaveh
<p>Inspired by the questions <a href="https://cstheory.stackexchange.com/questions/30537/nondeterministic-communication-complexity-of-set-disjointness">Nondeterministic communication complexity of set disjointness?</a>, I was wondering about the following: </p>

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

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

<blockquote>
  <p>Are there any known techniques that yield stronger lower bounds for deterministic protocols compared to nondeterministic protocols?</p>
</blockquote>

CC BY-SA 3.0
2015-02-19T08:55:41.980Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-02-19T10:35:00.683Z
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$.
András Salamon
<lower-bounds><communication-complexity>
Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?
MirkoMirkosovivisisic
# Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

(Asked by: username_0 on 2015-02-19)

Inspired by the questions [Nondeterministic communication complexity of set disjointness?](https://cstheory.stackexchange.com/questions/30537/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?

**Tags:** lower-bounds, communication-complexity
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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$.  

---

## 1 answers

### Answer by username_3 on 2015-02-19. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Apologies, I updated the question.  

---

