<p>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|$. </p>

<p>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.</p>

<p>The protocol goes as follows:</p>

<ol>
<li><p>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$.</p></li>
<li><p>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.</p></li>
<li><p>Bob estimates $c$ as $\frac at|\{i&lt;t:a_i\in B\}|$.</p></li>
</ol>

<p>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]$.</p>

<p>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$.</p>

<p>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):</p>

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

<p>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.</p>

CC BY-SA 4.0
2018-06-26T21:49:21.010Z
Thanks for the helpful answer! However, I just realized I forgot to mention that I am more interested in the case where the sets are small compared to $n$. Is there a way to make your protocol work in this setting?
Sorry for the confusion...
Or Meir
CC BY-SA 4.0
2018-06-27T06:57:35.300Z
What do you mean by additive approximation in such a setting?
Emil Jeřábek
CC BY-SA 4.0
2018-06-27T10:35:22.133Z
I would be interested in approximation up to any additive term that is meaningful, starting from a constant up to linear in the size of the sets.
Or Meir
CC BY-SA 4.0
2018-06-27T11:38:47.297Z
But error up to a constant fraction of the size of the set is the same as multiplicative approximation, isn’t it?
Emil Jeřábek
CC BY-SA 4.0
2018-06-27T11:39:46.013Z
Oh I see, you allow a fraction of the sizes of the original two sets, even if the intersection is much smaller.
Emil Jeřábek
CC BY-SA 4.0
2018-07-02T13:30:24.467Z
Since this is the best answer so far, I accept it.
Or Meir
CC BY-SA 4.0
2018-06-26T15:50:54.587Z
2018-06-28T15:05:36.883Z
2018-06-28T15:05:36.883Z
Emil Jeřábek
<p>[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.]</p>

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

<p>For example, here's one:</p>

<ol>
<li>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.</li>
<li>Alice and Bob each compute a <a href="https://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma" rel="nofollow noreferrer">$(k, \varepsilon)$-regularity partition</a> 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).</li>
<li>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 &gt; 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.</li>
</ol>

<p>If this sort of approximation is interesting to you, you might get more mileage out of other graph regularity lemmas, especially Frieze-Kannan.  <a href="https://www.ime.usp.br/~spschool2016/wp-content/uploads/2016/07/Rodl-Schacht.pdf" rel="nofollow noreferrer">Here</a> is a survey.</p>

CC BY-SA 4.0
2018-06-26T21:50:59.453Z
Thanks! The connection to regularity partitions is interesting.
Or Meir
CC BY-SA 4.0
2018-06-26T14:30:35.787Z
2018-06-26T16:31:23.970Z
2018-06-26T16:31:23.970Z
GMB
<p>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 (<a href="http://web.cs.ucla.edu/~sherstov/pdf/mfcs-disjointness.pdf" rel="nofollow noreferrer">see survey here</a>). In the case where the sets are of size $k$ for $k \ll n$, it is known that randomized protocols require $\Theta(k)$ bits (<a href="http://www.math.ias.edu/~avi/PUBLICATIONS/HastadWi2007.pdf" rel="nofollow noreferrer">see here</a>).</p>

<p>Consider now the variant in which Alice and Bob want to know the <em>size</em> 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 <em>multiplicative</em> approximation of the size. However, what happens if they want to compute an <em>additive approximation</em> of the size of the intersection? Is there any lower bound or upper bound known about this problem?</p>

<p>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$.</p>

CC BY-SA 4.0
2018-06-26T09:36:38.417Z
Additively c-approximating the intersection of two (n*2*c)-bit sets is at least as hard as computing the intersection of two n-bit sets; we reduce from the latter to the former by copying each bit 2c times and rounding the intersection size to the nearest multiple of c.
daniello
CC BY-SA 4.0
2018-06-26T09:39:24.783Z
I suppose the following reduction from classical set disjointness to the $\alpha$-additive approximation would give you lower bound. Suppose there protocol that achieves $\alpha=f(n)$ approximation. They players duplicate each of the original $n$ bits to $3f(n)$ bits. Hence if there is no intersection, the output is at most $f(n)$, and if there is an intersection it is at least $2 f(n)$. This gives a lower bound of $\Omega(\frac{n}{3f(n)})$.
Sajin Koroth
CC BY-SA 4.0
2018-06-26T10:34:19.243Z
Thanks! If you turn your comments to answers I will accept them.
Or Meir
CC BY-SA 4.0
2018-06-28T19:30:25.117Z
Don’t two subsets of $\{1, \ldots, n\}$ of size $n$ always intersect?
Geoffrey Irving
<reference-request><communication-complexity>
Communication complexity of approximating the size of set intersection
Or Meir
# Communication complexity of approximating the size of set intersection

(Asked by: username_0 on 2018-06-26)

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](http://web.cs.ucla.edu/~sherstov/pdf/mfcs-disjointness.pdf)). 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](http://www.math.ias.edu/~avi/PUBLICATIONS/HastadWi2007.pdf)).

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

**Tags:** reference-request, communication-complexity
> **Comments:**
> **username_1**: Additively c-approximating the intersection of two (n*2*c)-bit sets is at least as hard as computing the intersection of two n-bit sets; we reduce from the latter to the former by copying each bit 2c times and rounding the intersection size to the nearest multiple of c.  
> **username_2**: I suppose the following reduction from classical set disjointness to the $\alpha$-additive approximation would give you lower bound. Suppose there protocol that achieves $\alpha=f(n)$ approximation. They players duplicate each of the original $n$ bits to $3f(n)$ bits. Hence if there is no intersection, the output is at most $f(n)$, and if there is an intersection it is at least $2 f(n)$. This gives a lower bound of $\Omega(\frac{n}{3f(n)})$.  
> **username_0**: Thanks! If you turn your comments to answers I will accept them.  
> **username_3**: Don’t two subsets of $\{1, \ldots, n\}$ of size $n$ always intersect?  

---

## 2 answers

### Answer by username_4 on 2018-06-26. Score: 5 | Accepted answer

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
3. Bob estimates $c$ as $\frac at|\{i

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

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
6. Bob estimates $c$ as $\frac at|\{i

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.

> **Comments:**
> **username_0**: Thanks for the helpful answer! However, I just realized I forgot to mention that I am more interested in the case where the sets are small compared to $n$. Is there a way to make your protocol work in this setting? Sorry for the confusion...  
> **username_4**: What do you mean by additive approximation in such a setting?  
> **username_0**: I would be interested in approximation up to any additive term that is meaningful, starting from a constant up to linear in the size of the sets.  
> **username_4**: But error up to a constant fraction of the size of the set is the same as multiplicative approximation, isn’t it?  
> **username_4**: Oh I see, you allow a fraction of the sizes of the original two sets, even if the intersection is much smaller.  
> **username_0**: Since this is the best answer so far, I accept it.  

---

### Answer by username_5 on 2018-06-26. Score: 3

[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](https://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma) 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](https://www.ime.usp.br/~spschool2016/wp-content/uploads/2016/07/Rodl-Schacht.pdf) is a survey.

> **Comments:**
> **username_0**: Thanks! The connection to regularity partitions is interesting.  

---

