Complexidade de comunicação da aproximação do tamanho da interseção do conjunto

Considere o problema de interseção de conjuntos: Alice e Bob recebem um subconjunto de e gostariam de saber se seus conjuntos se cruzam. Esse é um problema canônico de complexidade da comunicação, e é sabido que protocolos aleatórios para esse problema requerem bits de comunicação ( consulte a pesquisa aqui ). No caso em que os conjuntos são do tamanho para , é sabido que protocolos aleatórios requerem bits ( veja aqui ).$\left\{ 1,\ldots, n\right\}$k k ≪ n Θ ( k $\Theta(n)$$k$$k \ll n$$\Theta(k)$

Considere agora a variante em que Alice e Bob querem saber o tamanho da interseção de seus conjuntos. Claramente, computar o tamanho exato reduz-se ao problema padrão de interseção de conjuntos, e isso vale mesmo se eles quiserem apenas calcular uma aproximação multiplicativa do tamanho. No entanto, o que acontece se eles querem calcular uma aproximação aditiva do tamanho da interseção? Existe algum limite inferior ou superior conhecido sobre esse problema?

Estou particularmente interessado nesta questão na configuração de pequenos conjuntos, ou seja, no caso em que os conjuntos são do tamanho .$k \ll n$

Vou dar dois limites superiores. Seja e os conjuntos dados a Alice e Bob, respectivamente, e coloque,,.B a = | Um | b = | B | c = | A ∩ B $A$$B$$a=|A|$$b=|B|$$c=|A\cap B|$

Primeiro, existe um protocolo aleatório que, dado e , calcula com probabilidade uma aproximação de até o erro aditivo , usando bits de comunicação e bits de aleatoriedade.$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)$

O protocolo é o seguinte:

1. Se , a parte que o vê encerra o protocolo e gera como a estimativa. Caso contrário, Alice e Bob comunicar e para o outro, e determinar qual é menor. Assumirei abaixo do wlog que .$d\ge\min\{a,b\}$$0$$a$$b$$a\le b$

2. Alice desenha amostras aleatórias uniformemente independentes , , e as envia para Bob.$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\}|$

O protocolo está correto pelos limites de Chernoff-Hoeffding: se denota a variável aleatória indicadora do evento , então , , são variáveis ​​iid com média . Assim, e da mesma forma para .$X_i$$a_i\in B$$X_i$$i<t$$p=c/a$

Agora, esses limites são um pouco inúteis se: : também existem limites de Chernoff que indicam que nos permitiria conviver com o número de amostras menores por um fator de aproximadamente . O problema é que é a mesma quantidade que queremos aproximar, portanto, não a conhecemos adiante. Isso pode ser remediado fazendo-se primeiro uma estimativa do de .$c\ll a$

Portanto, o protocolo aprimorado calcula com probabilidade uma aproximação aditiva de usando bits de comunicação e bits de aleatoriedade e é o seguinte (as constantes não são otimizadas):$\ge1-\epsilon$$d$$c$$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. O mesmo que acima.

2. Alice desenha amostras aleatórias de e as envia para Bob.$r=10(\log\epsilon^{-1})a/d$$A$

3. Bob conta quantas dessas amostras pertencem a e envia esse número, , para Alice.$B$$s$

4. Se , o protocolo termina com a saída .$as/r\le d/2$$0$

5. Alice desenha amostras aleatórias , envia para Bob.$t=10sa/d$$a_i\in A$$i<t$

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

Sem entrar em detalhes, os limites de Chernoff citados acima implicam que, com alta probabilidade, o valor de é , caso em que o protocolo não excede o custo declarado e calcula com alta probabilidade uma boa estimativa de por outra aplicação dos limites de Chernoff.$s/r$$\Theta(c/a)$$c$

[A resposta de Emil é claramente melhor e mais simples se você estiver interessado nesse tipo de erro, a menos que, por algum motivo, você precise que seu protocolo seja determinístico. Opa.]

Existem protocolos não triviais se você estiver interessado em aproximações aditivas do tipo para pequenas constantes .$\pm \delta n$$\delta > 0$

Por exemplo, aqui está um:

1. Alice e Bob interpretam cada conjunto como um gráfico em , concordando com algum mapeamento canônico dos itens possíveis do conjunto às arestas possíveis do gráfico.$\approx \sqrt{n}$$n$$n$
2. Alice e Bob calculam uma partição de de seu gráfico. Eles enviam mutuamente sua partição ( bits) mais a densidade do gráfico entre cada par de conjuntos de partições (por exemplo, bits, se forem relatadas densidades de até bits de precisão numérica).$(k, \varepsilon)$$\widetilde{O}(\sqrt{n})$$\widetilde{O}_{\varepsilon}(\sqrt{n})$$\sqrt{n}$
3. Alice e Bob agora descartam arestas que, para qualquer uma das duas partições: (a) têm ambos os pontos finais dentro de um dos conjuntos de partições, (b) têm ambos os pontos finais entre um par de conjuntos não regulares ou (c) cruzam um par de define na partição de Alice e na partição de Bob de modo que é extraordinariamente pequeno. Eles jogam fora, no máximo, uma fração constante dos itens, causando erro aditivo, mas pode ser arbitrariamente pequeno por escolha de$(S_1^A, S_2^A)$$(S_1^B, S_2^B)$ $$\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$. As interseções entre os itens restantes podem ser estimadas de perto por métodos estatísticos padrão, uma vez que os gráficos entre esses conjuntos obedecem às estatísticas de um gráfico bipartido aleatório com a densidade especificada.

Se esse tipo de aproximação lhe interessar, você poderá obter mais milhas de outros lemas de regularidade de gráfico, especialmente Frieze-Kannan. Aqui está uma pesquisa.