Complejidad de comunicación de aproximar el tamaño de la intersección establecida

Considere el problema de la intersección de conjuntos: Alice y Bob obtienen cada uno un subconjunto de $\left\{ 1,\ldots, n\right\}$ , y les gustaría saber si sus conjuntos se intersecan. Este es un problema canónico de la complejidad de la comunicación, y es bien sabido que los protocolos aleatorizados para este problema requieren $\Theta(n)$ bits de comunicación ( ver encuesta aquí ). En el caso de que los conjuntos sean de tamaño $k$ para $k \ll n$ , se sabe que los protocolos aleatorios requieren bits $\Theta(k)$ ( ver aquí ).

Considere ahora la variante en la que Alice y Bob quieren saber el tamaño de la intersección de sus conjuntos. Claramente, calcular el tamaño exacto se reduce al problema estándar de intersección de conjuntos, y esto se cumple incluso si solo desean calcular una aproximación multiplicativa del tamaño. Sin embargo, ¿qué sucede si desean calcular una aproximación aditiva del tamaño de la intersección? ¿Hay algún límite inferior o superior conocido sobre este problema?

Estoy particularmente interesado en esta pregunta en la configuración de conjuntos pequeños, es decir, el caso en que los conjuntos son de tamaño $k \ll n$ .

Daré dos límites superiores. Deje que y B sean los conjuntos dados a Alice y Bob, respectivamente, y ponga a = | A | , b = | B | , c = | A ∩ B | .$A$$B$$a=|A|$$b=|B|$$c=|A\cap B|$

$d>0$$\epsilon>0$$\ge1-\epsilon$$c$$d$$O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log n\log\epsilon^{-1}\Bigr)$$O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$

El protocolo es el siguiente:

1. Si , la parte que lo ve termina el protocolo y genera como la estimación. De lo contrario, Alice y Bob comunican y el uno al otro, y determinar que es más pequeño. Asumiré a continuación wlog que .0 a b a ≤ $d\ge\min\{a,b\}$$0$$a$$b$$a\le b$

2. Alice dibuja muestras independientes aleatoriamente uniformes , , y las envía a Bob.a i ∈ A i < $t=\log(2\epsilon^{-1})a^2/(2d^2)$$a_i\in A$$i<t$

3. Bob estima como.$c$$\frac at|\{i<t:a_i\in B\}|$

El protocolo es correcto según los límites de Chernoff-Hoeffding: si denota la variable aleatoria indicadora del evento , entonces , , son variables iid con media . Por lo tanto, y de manera similar para .a i ∈ B X i i < t p = c / a Pr [ a ¯ X ≤ c - d ] = Pr [ ¯ X ≤ p - $X_i$$a_i\in B$$X_i$$i<t$$p=c/a$Pr[a ¯ X ≥c+d

Ahora, estos límites son algo inútiles si : también hay variantes de Chernoff que indican lo que nos permitiría superar el número de muestras más pequeñas en un factor de aproximadamente . El problema es que es la cantidad que queremos aproximar, por lo tanto, no lo sabemos con anticipación. Esto puede remediarse haciendo primero un cálculo aproximado de .Pr [ ¯ X ≤ p - δ $c\ll a$ tpp=c/a

Entonces, el protocolo mejorado calcula con probabilidad una aproximación aditiva de usando bits de comunicación, y bits de aleatoriedad, y se realiza de la siguiente manera (las constantes no están optimizadas):d c O ( min { a , b $\ge1-\epsilon$$d$$c$O(min{a,b$O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log n\log\epsilon^{-1}\Bigr)$$O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$

1. Lo mismo que arriba.

2. Alice extrae muestras aleatorias de y las envía a Bob.$r=10(\log\epsilon^{-1})a/d$$A$

3. Bob cuenta cuántas de estas muestras pertenecen a y envía este número, , a Alice.$B$$s$

4. Si , el protocolo termina con la salida .$as/r\le d/2$$0$

5. Alice dibuja muestras aleatorias , , y se las envía a Bob.a i ∈ A i < $t=10sa/d$$a_i\in A$$i<t$

6. Bob estima como.$c$$\frac at|\{i<t:a_i\in B\}|$

Sin entrar en detalles, los límites de Chernoff citados anteriormente implican que con alta probabilidad, el valor de es , en cuyo caso el protocolo no excede el costo establecido, y se calcula con alta probabilidad una buena estimación de por otra aplicación de los límites de Chernoff.$s/r$$\Theta(c/a)$$c$

[La respuesta de Emil es claramente mejor y más simple si está interesado en este tipo de error, a menos que por alguna razón necesite que su protocolo sea determinista. ¡Vaya!]

Existen protocolos no triviales si está interesado en aproximaciones aditivas de tipo para constantes pequeñas .$\pm \delta n$$\delta > 0$

Por ejemplo, aquí hay uno:

1. Alice y Bob interpretan su conjunto como un gráfico sobre nodos nodos acordando un mapeo canónico de los posibles elementos del conjunto a los bordes posibles del gráfico.$\approx \sqrt{n}$$n$$n$
2. Alice y Bob calculan una partición de de su gráfico. Se envían entre sí su partición ( bits) más la densidad de su gráfico entre cada par de conjuntos de particiones (por ejemplo, bits, si se informan densidades de hasta bits de precisión numérica).$(k, \varepsilon)$$\widetilde{O}(\sqrt{n})$$\widetilde{O}_{\varepsilon}(\sqrt{n})$$\sqrt{n}$
3. Alice y Bob ahora descartan los bordes que, para cualquiera de las dos particiones: (a) tienen ambos puntos finales dentro de uno de los conjuntos de particiones, (b) tienen ambos puntos finales entre un par de conjuntos no regulares, o (c) cruzan un par de establece en la partición de Alice y en la partición de Bob de modo que es inusualmente pequeño. Desecharán a lo sumo una fracción constante de los elementos, causando error aditivo, pero puede hacerse arbitrariamente pequeño mediante la elección de$(S_1^A, S_2^A)$$(S_1^B, S_2^B)$δ>0±δnδk, $$\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\}$$ $\delta > 0$$\pm \delta n$$\delta$$k, \varepsilon$. Las intersecciones entre los elementos restantes se pueden estimar estrechamente mediante métodos estadísticos estándar, ya que los gráficos entre estos conjuntos obedecen a las estadísticas de un gráfico bipartito aleatorio con la densidad dada.

Si este tipo de aproximación es interesante para usted, puede obtener más kilometraje de otros lemas de regularidad de gráficos, especialmente Frieze-Kannan. Aquí hay una encuesta.