Nondeterministic communication complexity of set disjointness?

Question

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 (preprint). 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)$.

Answer 1

$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)