Complexidade de comunicação aleatória unidirecional de disjunção

Estou procurando uma referência para a (clássica) complexidade de comunicação aleatória unidirecional quando o universo pode ser grande. Digamos que Alice e Bob tenham conjuntos de tamanho escolhidos entre um universo de tamanho e Bob queira determinar se a interseção de seus conjuntos está vazia ou não. Gostaria prov de erro , por exemplo. $m$ $U$ $<1/3$

Posso encontrar o limite inferior padrão de e alguns trabalhos sobre a complexidade da comunicação bidirecional, mas há uma referência para algo mais restrito para a via única? $\Omega(m)$

EDIT: Eu deveria ter especificado que estou interessado no modelo de aleatoriedade privada (não de moeda pública).

cc.complexity-theory reference-request lower-bounds communication-complexity Rafael
fonte

Os conjuntos são escolhidos aleatoriamente ou apenas a estratégia de comunicação?

precisa saber é o seguinte

A randomização refere-se apenas ao fato de que Alice e Bob podem usar bits aleatórios.

Raphael

Você está realmente considerando a comunicação unidirecional (Alice envia uma mensagem para Bob, que então envia a resposta) ou comunicação "simultânea" (Alice e Bob enviam uma mensagem para um árbitro que anuncia a resposta). No primeiro caso, público e privado a aleatoriedade é a mesma e, portanto, parece que as respostas abaixo (ou seja, o blog de Mihai) resolvem a questão.

Noam

É o primeiro caso de comunicação unidirecional, como você define, no qual estou interessado. Espero algo apertado em toda a gama de tamanhos de universo. Se bem entendi, o post de Mihai nos dá um limite superior de

e temos um limite inferior de

O (m \log m + \log U)

$O(m \log{m} + \log{U})$

que ainda deixa uma lacuna.

min ((\binom{U}{m}), m \log m)

$\min(\binom{U}{m}, m\log{m})$

Raphael

Quero dizer

claro.

Ω (min (\log (\binom{U}{m}), m \log m))

$\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$

Raphael

Respostas:

A resposta é . No modelo de moedas públicas, temos (como descrito acima) . Como Yuval sugeriu acima, para o limite superior no modelo de moedas privadas, precisamos apenas de um aditivo bits (consulte o teorema 3.14 do livro K&N ), onde $\Theta(m\log m + \log\log |U|)$ $\Theta(m\log m)$ $O(\log n)=O(\log m + \log\log |U|)$ $n$ é o comprimento da codificação da entrada ( ). Para o limite inferior adicional de no modelo de moeda privada, basta concentrar-se no caso (como os outros itens podem ser corrigidos para serem todos diferentes), que é apenas a igualdade função no cadeias de bits, cuja complexidade da moeda privada é logarítmica nisso (exemplo 3.9 em K&N). $n=m\log|U|$ $\Omega(\log\log |U|)$ $m=1$ $\log |U|$

Noam
fonte

\log (\binom{U}{m})

$\log {\binom{U}{m}}$

m \log m

$m\log{m}$

U

$U$

m

$m$

U = m

$U=m$

U

$U$

m^{1 + ϵ}

$m^{1+\epsilon}$

isso resolve a questão :-) #

596 Marcos Villagra

\log \log | X | \leq R (f)

$\log \log |X| \le R(f)$

\log (\binom{U}{m})

$\log{\binom{U}{m}}$

U = m \log m

$U = m \log{m}$

$\Omega(n)$

$f$ $R_\epsilon^1(f)=\Omega(VC(f))$ $R_\epsilon^1(f)$ $f$ $\epsilon$ $VC(f)$ $f$ $VC(DISJ)=n$ $\Omega(n\log n)$

Marcos Villagra
fonte

O (n \log n)

$O(n\log n)$

Existe um truque que mostra que a aleatoriedade pública é igual à aleatoriedade privada: use um Chernoff vinculado para mostrar que existe um espaço de amostra de tamanho polinomial [no logaritmo do número de entradas possíveis] que aproxima a probabilidade de sucesso "bem o suficiente" em todas as entradas; Alice escolhe um desses pontos e envia seu índice de tamanho logarítmico para Bob. Esse truque não se aplica diretamente nesse caso (já que existem infinitas entradas), mas pode ser adaptado de alguma forma.

Yuval Filmus

Obrigado! Eu deveria ter especificado aleatoriedade particular na pergunta. Corrigindo agora.

Raphael

$\log \log |\text{size}|$ $\log \log {U \choose m}$ $\log \log U$ $m$

$m + \log \log U$

domotorp
fonte