Communication complexity of approximating the size of set intersection 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$.
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&gt;0$ and $\epsilon&gt;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:


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$.
Alice draws $t=\log(2\epsilon^{-1})a^2/(2d^2)$ independent uniformly random samples $a_i\in A$, $i&lt;t$, and sends them to Bob.
Bob estimates $c$ as $\frac at|\{i&lt;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&lt;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]&amp;\le\exp\left(-\frac{\delta^2}{2p}t\right),\\
\Pr\left[\overline X\ge p+\delta\right]&amp;\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):


Same as above.
Alice draws $r=10(\log\epsilon^{-1})a/d$ random samples from $A$, and sends them to Bob.
Bob counts how many of these samples belong to $B$, and sends this number, $s$, to Alice.
If $as/r\le d/2$, the protocol terminates with output $0$.
Alice draws $t=10sa/d$ random samples $a_i\in A$, $i&lt;t$, and sends them to Bob.
Bob estimates $c$ as $\frac at|\{i&lt;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.