Lower Bounds for the Set Disjointness Problem

Question

Consider the set disjointness problem. Alice and Bob hold n-bit strings $a$ and $b$ respectively. They would like to compute the function $$ \text{Dis}(a,b) = \begin{cases} 0 &\text{if } \exists i : a_i = b_i = 1 \\ 1 & \text{Otherwise}\\ \end{cases} $$

It is well known that this problem has communication complexity exactly $\Theta(n)$ (see here for example). This means that it cannot be solved with communication overhead sublinear in $n$.

Many times this result is informally stated as "Computing disjointness has communication overhead linear in the size of the inputs"

Question: How do I go from the formal definition and result for set disjointness to the informal statement above. My issue is the following: Assume Alice and Bob hold sets of 64-bit integers. In this case writing them as characteristic bit vectors would require them to send around 2^64 bits. However, clearly I can trivially solve the problem by sending my total set, which would have a communication overhead of $\text{set-size} \cdot 64$. How is this communication overhead related to the bit-strings of the set disjointness problem?

Answer 1

That's simply a different problem. The set disjointness problem is defined, by common agreement, to be the problem where the universe has size $n$ and the inputs (sets) are represented as a bitvector of length $n$. In other words, when you hear the phrase "set disjointness problem", you can know that's what they're referring to, and not the problem you care about.

It's fair to ask about the communication complexity of your problem. I don't know what its communication complexity is. There is no reason to assume your problem will necessarily have the same complexity as the set disjointness problem.

(There's a natural randomized protocol for your problem: if Alice and Bob each have a set of $n$ 64-bit integers randomly pick a universal hash function $f$ from the space of 64-bit integers to the set $\{1,2,\dots,2n\}$, transmit a description of $f$, hash the elements, and check disjointness of the hashed elements. If there is a common element among the hashes, use binary search to find all common elements and check if the unhashed elements match as well. The expected communication cost is $\Theta(n)$. It's also clear that any algorithm must have communication complexity $\Omega(n)$. This still leaves open what is the communication complexity for deterministic protocols, or the worst-case communication complexity for randomized protocols.)

Answer 2

This answer refers to a previous version of the question, in which the condition $a_i = b_i = 1$ was replaced by the condition $a_i = b_i$.

First of all, your problem is EQUALITY in disguise (complement one of the vectors to see why). The complexity of EQUALITY is still $\Theta(n)$ in the deterministic case, but it drops down to $\Theta(\log n)$ in the randomized setting.

Second, in communication complexity we are almost always interested in worst case complexity. Indeed, for any two inputs $x,y$ you can concoct a protocol which solves the problem correctly for them using only $O(1)$ communication, whatever the problem is (exercise). Your protocol is actually worse than the trivial protocol when Alice's input is very dense (depending on how Alice encodes her input).

You can define average case measures in communication complexity in various ways. The two ways that come to mind are:

• The average number of bits communicated given a specific distribution of Alice and Bob's inputs.
• The maximum, over all inputs, of the average number of bits communicated (in a randomized protocol).

In both cases, by truncating the protocols, we get a randomized protocol with some error probability and a worst case guarantee. This shows that for set disjointness, you cannot save anything in this way (since its randomized complexity is still $\Theta(n)$). For EQUALITY, savings are possible, though with a protocol different than what you described (if you're interested, look up the randomized protocols for EQUALITY, and try to fit them into these average case settings).