Communication complexity of approximating the size of set intersection

Question

Consider the set-intersection problem: Alice and Bob each get a subset of $\left\{ 1,\ldots, n\right\}$, and they would like to know whether their sets intersect. This is a canonical problem of communication complexity, and it is well-known that randomized protocols for this problem require $\Theta(n)$ bits of communication (see survey here). In the case where the sets are of size $k$ for $k \ll n$, it is known that randomized protocols require $\Theta(k)$ bits (see here).

Consider now the variant in which Alice and Bob want to know the size of the intersection of their sets. Clearly, computing the exact size reduces to the standard set-intersection problem, and this holds even if they only want to compute a multiplicative approximation of the size. However, what happens if they want to compute an additive approximation of the size of the intersection? Is there any lower bound or upper bound known about this problem?

I am particularly interested in this question in the setting of small sets, i.e., the case where the sets are of size $k \ll n$.

Answer 1

I will give two upper bounds. Let $A$ and $B$ be the sets given to Alice and Bob, respectively, and put $a=|A|$, $b=|B|$, $c=|A\cap B|$.

First, there is a randomized protocol that, given $d>0$ and $\epsilon>0$, computes with probability $\ge1-\epsilon$ an approximation of $c$ up to additive error $d$, using $O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log n\log\epsilon^{-1}\Bigr)$ bits of communication, and $O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$ bits of randomness.

The protocol goes as follows:

1. If $d\ge\min\{a,b\}$, the party who sees it terminates the protocol and outputs $0$ as the estimate. Otherwise, Alice and Bob communicate $a$ and $b$ to each other, and determine which is smaller. I will assume below w.l.o.g. that $a\le b$.

2. Alice draws $t=\log(2\epsilon^{-1})a^2/(2d^2)$ independent uniformly random samples $a_i\in A$, $i<t$, and sends them to Bob.

3. Bob estimates $c$ as $\frac at|\{i<t:a_i\in B\}|$.

The protocol is correct by the Chernoff–Hoeffding bounds: if $X_i$ denotes the indicator random variable of the event $a_i\in B$, then $X_i$, $i<t$, are i.i.d. variables with mean $p=c/a$. Thus, $$\Pr\left[a\overline X\le c-d\right]=\Pr\left[\overline X\le p-\tfrac da\right]\le\exp\left(-2\left(\tfrac da\right)^2t\right)\le\frac\epsilon2,$$ and similarly for $\Pr\bigl[a\overline X\ge c+d\bigr]$.

Now, these bounds are somewhat wasteful if $c\ll a$: there are also variant Chernoff bounds stating $$\begin{align} \Pr\left[\overline X\le p-\delta\right]&\le\exp\left(-\frac{\delta^2}{2p}t\right),\\ \Pr\left[\overline X\ge p+\delta\right]&\le\exp\left(-\frac{\delta^2}{3p}t\right),\qquad\delta\le p, \end{align}$$ which would allow us to get by with the number of samples $t$ smaller by a factor of roughly $p$. The problem is that $p=c/a$ is the very quantity we want to approximate, hence we do not know it ahead. This can be remedied by making first a ball-park estimate of $c$.

So, the improved protocol computes with probability $\ge1-\epsilon$ an additive $d$-approximation of $c$ using $O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log n\log\epsilon^{-1}\Bigr)$ bits of communication, and $O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$ bits of randomness, and it goes as follows (the constants are not optimized):

1. Same as above.

2. Alice draws $r=10(\log\epsilon^{-1})a/d$ random samples from $A$, and sends them to Bob.

3. Bob counts how many of these samples belong to $B$, and sends this number, $s$, to Alice.

4. If $as/r\le d/2$, the protocol terminates with output $0$.

5. Alice draws $t=10sa/d$ random samples $a_i\in A$, $i<t$, and sends them to Bob.

6. Bob estimates $c$ as $\frac at|\{i<t:a_i\in B\}|$.

Without going into the details, the Chernoff bounds quoted above imply that with high probability, the value of $s/r$ is $\Theta(c/a)$, in which case the protocol does not exceed the stated cost, and it computes with high probability a good estimate of $c$ by another application of Chernoff bounds.

Answer 2

[Emil's answer is clearly better and simpler if you're interested in this type of error, unless for some reason you need your protocol to be deterministic. Oops.]

There are nontrivial protocols if you're interested in additive approximations of type $\pm \delta n$ for small constants $\delta > 0$.

For example, here's one:

1. Alice and Bob each interpret their set as a graph over $\approx \sqrt{n}$ nodes by agreeing on some canonical mapping from the $n$ possible set items to the $n$ possible edges of the graph.
2. Alice and Bob each compute a $(k, \varepsilon)$-regularity partition of their graph. They send each other their partition ($\widetilde{O}(\sqrt{n})$ bits) plus the density of their graph between each pair of partition sets (e.g. $\widetilde{O}_{\varepsilon}(\sqrt{n})$ bits, if densities are reported up to $\sqrt{n}$ bits of numberical precision).
3. Alice and Bob now discard edges that, for either of the two partitions:(a) have both endpoints within one of the partition sets, (b) have both endpoints between a non-regular set pair, or (c) cross a pair of sets $(S_1^A, S_2^A)$ in Alice's partition and $(S_1^B, S_2^B)$ in Bob's partition such that $$\max\left\{ \min\{\left| S_1^A \cap S_1^B \right|, \left|S_2^A \cap S_2^B\right|\}, \min\{\left|S_1^A \cap S_2^B\right|, \left| S_2^A \cap S_1^B \right|\} \right\}$$ is unusually small. They will throw away at most a constant $\delta > 0$ fraction of the items, causing $\pm \delta n$ additive error, but $\delta$ can be made arbitrarily small by choice of $k, \varepsilon$. The intersections among remaining items can be closely estimated by standard statistical methods, since the graphs between these sets obey the statistics of a random bipartite graph with the given density.

If this sort of approximation is interesting to you, you might get more mileage out of other graph regularity lemmas, especially Frieze-Kannan. Here is a survey.