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?

  • $\begingroup$ As Yuval Filmus points out in his answer, your definition of $\text{Dis}$ is not the set disjointness problem. Perhaps you meant $1$ if $\exists i : a_i=b_i=1$; 0 otherwise. $\endgroup$ – D.W. Jul 24 '18 at 7:34
  • $\begingroup$ Sorry. I fixed my description of the disjointness problem. $\endgroup$ – Cryptonaut Jul 24 '18 at 9:59
  • $\begingroup$ For the revised question, note that if the elements of a set are in the range $0$ to $2^{64}-1$, then the set size can be up to $2^{64}$ elements, so for set sizes that are greater than $2^{64}/64$, sending the characteristic vector is more efficient. As Yuval Filmus points out, the setup requires using worst-case analysis. $\endgroup$ – András Salamon Jul 24 '18 at 12:29

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.