集合交点の大きさを近似する通信複雑度

アリスとボブはそれぞれ$ left {1、 ldots、n right }
$の部分集合を取得し、それらの集合が交差するかどうかを知りたいと思う。これは通信の複雑さの標準的な問題であり、この問題の無作為化されたプロトコルには通信の$
Theta(n)$ビットが必要であることはよく知られています(アンケートはこちらをご覧ください)。セットが$ k ll n
$のサイズ$ k $である場合、無作為プロトコルは$ Theta(k)$ビットを必要とすることが知られている(ここを参照)。

アリスとボブがセットの交差のサイズを知りたいと思っている変形を考えてみましょう。明らかに、正確なサイズを計算することは、標準的な集合交差問題になります。これは、サイズの
multiplicative
近似だけを計算したい場合でも有効です。しかし、交差点のサイズの近似値を計算したい場合はどうなりますか?この問題について既知の下限または上限がありますか?

私は小さなセットの設定、すなわちセットがサイズ$ k ll n $の場合にこの問題に特に関心があります。

ベストアンサー

私は2つの上限を与えます。 AliceとBobにそれぞれ与えられた集合を$ A $と$ B $とし、$ 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
$OBigl(left(frac{min{a,b}}dright)^2log
nlogepsilon^{-1}Bigr)$ bits of communication, and
$OBigl(left(frac{min{a,b}}dright)^2log
min{a,b}logepsilon^{-1}Bigr)$ bits of randomness.

プロトコルは次のようになります。

  1. If $dgemin{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 $ale b$.

  2. Alice draws $t=log(2epsilon^{-1})a^2/(2d^2)$ independent
    uniformly random samples $a_iin 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_iin
B$, then $X_i$, $i

Now, these bounds are somewhat wasteful if $cll a$: there are
also variant Chernoff bounds stating $$begin{align}
Prleft[overline Xle
p-deltaright]&leexpleft(-frac{delta^2}{2p}tright),\
Prleft[overline Xge
p+deltaright]&leexpleft(-frac{delta^2}{3p}tright),qquaddeltale
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
$OBigl(frac{min{a,b}}dleft(1+frac cdright)log
nlogepsilon^{-1}Bigr)$ bits of communication, and
$OBigl(frac{min{a,b}}dleft(1+frac cdright)log
min{a,b}logepsilon^{-1}Bigr)$ bits of randomness, and it goes
as follows (the constants are not optimized):

  1. Same as above.

  2. Alice draws $r=10(logepsilon^{-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/rle d/2$, the protocol terminates with output $0$.

  5. Alice draws $t=10sa/d$ random samples $a_iin 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.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です