Communication complexity of approximating the size of set intersection
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.