<p>$N^1(DISJ_n) \geq n$.</p>

<p>The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$.  In the fooling set technique, you create a set of input pairs and show that each must lie in distinct monochromatic rectangles.  </p>

<p>In this case, look at the set of input pairs $\{(A,\bar{A}) : A \subseteq [n]\}$.  It is not too hard to show that $(A, \bar{A}), (B, \bar{B})$ must lie in different monochromatic rectangles if $A,B$ are distinct.  Hence, to cover the $1$-inputs, we need at least $2^n$ monochromatic rectangles.</p>

<p>Using $N^1(f) = \log_2(C^1(f))$, we get that $N^1(DISJ_n) \geq n$.</p>

<p>(This example is Example 1.23 from Kushilevitz/Nisan)</p>

CC BY-SA 3.0
2015-02-18T17:31:47.517Z
2015-02-18T17:31:47.517Z
Joshua Brody
<p>In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}_n$.
(Here $\text{DISJ}_n$ is the $n$-element set disjointness function; the parties are each given $n$-bit Boolean vectors $x$ and $y$, and have to decide whether there is some index $i$ so that $x_i = y_i = 1$.)</p>

<p>In contrast, for nondeterministic protocols in the two-party setting, the best lower bound I've been able to find in the literature is $\Omega(n^{1/2})$ bits: Alexander A. Sherstov, <em>Communication Lower Bounds Using Directional Derivatives</em>, JACM 2014, doi:<a href="http://dx.doi.org/10.1145/2629334">10.1145/2629334</a> (<a href="http://www.cs.ucla.edu/~sherstov/pdf/directional.pdf">preprint</a>).
A large gap remains between this and the trivial upper bound of $n+1$ bits.</p>

<p>Sherstov's bound is for multiparty protocols.</p>

<blockquote>
  <p>Is a better lower bound known for the 2-party case?</p>
</blockquote>

<p>Here follows a simple (folklore?) argument that $\Omega(n/\log n)$ bits are required; I am looking for a reference for this so I can cite it, or ideally a stronger $\omega(n/\log n)$ bound.</p>

<hr>

<p>A standard result (e.g. Theorem 2.11 in the Kushilevitz/Nisan textbook) is that $$D(f) \le O(N^0(f)N^1(f)),$$ where $N^1(f)$ is the nondeterministic communication complexity of $f$ and $N^0(f)$ is the co-nondeterministic communication complexity.
For $f = \text{DISJ}_n$ it is easy to see that $N^0(f) = O(\log n)$, by guessing the index of a common element.
Hence there are constants $C_1,C_2,C_3$ such that for all sufficiently large $n$,
$$C_1 n \le D(f) \le C_2 N^0(f)N^1(f) \le C_2 C_3(\log n)N^1(f).$$
Hence $N^1(f) \ge \Omega(n/\log n)$.</p>

<cc.complexity-theory><lower-bounds><communication-complexity>
Nondeterministic communication complexity of set disjointness?
András Salamon
# Nondeterministic communication complexity of set disjointness?

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

In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}\_n$.
(Here $\text{DISJ}\_n$ is the $n$-element set disjointness function; the parties are each given $n$-bit Boolean vectors $x$ and $y$, and have to decide whether there is some index $i$ so that $x\_i = y\_i = 1$.)

In contrast, for nondeterministic protocols in the two-party setting, the best lower bound I've been able to find in the literature is $\Omega(n^{1/2})$ bits: Alexander A. Sherstov, *Communication Lower Bounds Using Directional Derivatives*, JACM 2014, doi:[10.1145/2629334](http://dx.doi.org/10.1145/2629334) ([preprint](http://www.cs.ucla.edu/~sherstov/pdf/directional.pdf)).
A large gap remains between this and the trivial upper bound of $n+1$ bits.

Sherstov's bound is for multiparty protocols.

> Is a better lower bound known for the 2-party case?

Here follows a simple (folklore?) argument that $\Omega(n/\log n)$ bits are required; I am looking for a reference for this so I can cite it, or ideally a stronger $\omega(n/\log n)$ bound.

---

A standard result (e.g. Theorem 2.11 in the Kushilevitz/Nisan textbook) is that $$D(f) \le O(N^0(f)N^1(f)),$$ where $N^1(f)$ is the nondeterministic communication complexity of $f$ and $N^0(f)$ is the co-nondeterministic communication complexity.
For $f = \text{DISJ}\_n$ it is easy to see that $N^0(f) = O(\log n)$, by guessing the index of a common element.
Hence there are constants $C\_1,C\_2,C\_3$ such that for all sufficiently large $n$,
$$C\_1 n \le D(f) \le C\_2 N^0(f)N^1(f) \le C\_2 C\_3(\log n)N^1(f).$$
Hence $N^1(f) \ge \Omega(n/\log n)$.

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


---

## 1 answers

### Answer by username_1 on 2015-02-18. Score: 9 | Accepted answer

$N^1(DISJ\_n) \geq n$.

The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$. In the fooling set technique, you create a set of input pairs and show that each must lie in distinct monochromatic rectangles.

In this case, look at the set of input pairs $\{(A,\bar{A}) : A \subseteq [n]\}$. It is not too hard to show that $(A, \bar{A}), (B, \bar{B})$ must lie in different monochromatic rectangles if $A,B$ are distinct. Hence, to cover the $1$-inputs, we need at least $2^n$ monochromatic rectangles.

Using $N^1(f) = \log\_2(C^1(f))$, we get that $N^1(DISJ\_n) \geq n$.

(This example is Example 1.23 from Kushilevitz/Nisan)


---

