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


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


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.