8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – daniello Jun 26 '18 at 9:36
  • 1
    $\begingroup$ 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)})$. $\endgroup$ – Sajin Koroth Jun 26 '18 at 9:39
  • $\begingroup$ Thanks! If you turn your comments to answers I will accept them. $\endgroup$ – Or Meir Jun 26 '18 at 10:34
  • 1
    $\begingroup$ Don’t two subsets of $\{1, \ldots, n\}$ of size $n$ always intersect? $\endgroup$ – Geoffrey Irving Jun 28 '18 at 19:30
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Or Meir Jun 26 '18 at 21:49
  • $\begingroup$ What do you mean by additive approximation in such a setting? $\endgroup$ – Emil Jeřábek Jun 27 '18 at 6:57
  • $\begingroup$ 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. $\endgroup$ – Or Meir Jun 27 '18 at 10:35
  • $\begingroup$ But error up to a constant fraction of the size of the set is the same as multiplicative approximation, isn’t it? $\endgroup$ – Emil Jeřábek Jun 27 '18 at 11:38
  • $\begingroup$ Oh I see, you allow a fraction of the sizes of the original two sets, even if the intersection is much smaller. $\endgroup$ – Emil Jeřábek Jun 27 '18 at 11:39
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! The connection to regularity partitions is interesting. $\endgroup$ – Or Meir Jun 26 '18 at 21:50

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.