Limite superior para defina disjunta sob distribuições de produtos

Question

Para o problema de conjunto disjunção no modelo 2-party de complexidade de comunicação, Alice é dada uma entrada $ X $ e Bob é dada entrada $ y $ , $ x $ e $ y $ < span class="matemática-recipiente"> $ N $ bitstrings -length (amostrados a partir de alguma distribuição), que são interpretados como subconjuntos de $ [N] $ , ou seja, $ x_i= 1 $ significa que o $ i $ pouco -ésimo de $ x $ está no subconjunto. O objetivo é que Alice e Bob a responder se os subconjuntos representados por $ X $ e $ Y $ são disjunto usando o mínimo de comunicação possível. Sabe-se que $ \ ômega (n) $ bits são necessários no pior caso para protocolos randomizados.

Me deparei com este projecto do livro Comunicação Complexidade por Anup Rao e Amir Yehudayoff , onde Exercício 6.8 menciona que set disjunção 2-party pode ser resolvido com um esperado número de $ o (n ^ {2 / 3} \ log ^ 2 n) $ bits se as entradas de Alice e Bob são amostradas de forma independente.

.

Considere o seguinte protocolo. Se houver uma coordenada $ j \ em [n] $ de tal modo que $ H (X_j) $ e $ H (Y_j) $ são ambos pelo menos $ \ epsilon $ , em seguida, Alice e Bob comunicar $ X_j, Y_j $ . Eles condicionam os valores que eles vêem e repetem esta etapa até que nenhuma coordenada não seja encontrada. Neste ponto, Alice e Bob usam o teorema de codificação de Shannon para codificar $ x $ , $ y $ . Mostram como definir $ \ epsilon $ para que a comunicação esperada pode delimitada por $ n ^ {2/3} \ log ^ 2 n $ . DICA: Use o fato de que $ h (x_j) \ GE \ Epsilon $ implica que $ pr [x_j= 1] \ ge \ Omega (\ epsilon / (\ log (1 / ε))) $ .

Suponho que a ideia é a primeira a comunicar todos os índices, onde $ X $ e $ Y $ tem A grande entropia e depois usar o fato de que os índices restantes devem ter uma pequena entropia. No entanto, os detalhes do protocolo e onde a independência da $ x $ e $ y $ está chegando , não são claras para mim.

Answer 1

Durante a primeira fase do algoritmo, os jogadores aumentam a coordenada de alta entropia. Eles trocam $ o (1) $ bits, e param em cada passo com probabilidade $ \ ômega (\ epsilon ^ 2 / \ log ^ 2 (1 / \ epsilon)) $ (aqui usamos independência). Daí esta fase usa no máximo $ o (\ log ^ 2 (1 / \ epsilon) / \ epsilon ^ 2) $ bits na expectativa. A segunda fase usa $ O (n \ epsilon) $ bits. No total, usamos esses muitos bits na expectativa: $$ O (\ log ^ 2 (1 / \ epsilon) / \ epsilon ^ 2 + \ epsilon n). $$ Escolha $ \ epsilon= 1 / n ^ {1/3} $ para obter o limite declarado.

Sem independência, não temos nenhum controle sobre a probabilidade de parada em cada etapa da primeira fase. Por exemplo, pode ser que $ x $ é amostrado uniformemente à aleatoriamente, e $ y $ é o negação de $ x $ . Neste caso, a primeira fase nunca vai parar, e assim o protocolo sempre usará $ 2N $ bits.

como um lado, o limite superior pode ser melhorado para $ o (\ sqrt {n} \ log n) $ , que quase combina com o limite inferior $ \ ômega (\ sqrt {n}) $ (a lacuna pode ter sido fechada na literatura). Ver notas de palestras de Prahladh Harsha < / a>.