Suponha que Alice receba um subconjunto e Bob receba T ⊆ { 1 , … , n } . É prometido que | S ∩ T | = 1 . Qual é a complexidade da comunicação aleatória para determinar o elemento comum S ∩ T ?
Meu interesse nisso é o seguinte. O custo de comunicação zero desse problema é já que Alice e Bob podem adivinhar S ∩ T usando moedas públicas e abortar se acharem errado. No entanto, não consigo pensar em um protocolo de comunicação de custo O ( log n ) . Como não se sabe se o custo de comunicação zero é muito menor que o custo de comunicação aleatória, estou pensando que estou perdendo algo óbvio aqui.
O custo de comunicação zero é definido da seguinte maneira. Depois que Alice e Bob recebem suas contribuições, eles não devem se comunicar. No entanto, eles compartilham moedas públicas e podem responder com "abortar". Se nem aborts partido, eles devem fornecer a resposta correta com de probabilidade. O custo da comunicação zero é o log negativo da probabilidade de não abortar. No arxiv: 1204.1505 , é mostrado (entre outras coisas) que quase todos os limites inferiores conhecidos da complexidade da comunicação são de fato limites inferiores para a comunicação zero.
Atualização: @Shitikanth mostrou que a complexidade da comunicação é . Então, aparentemente, isso cria uma lacuna entre o custo de comunicação e o custo de comunicação zero. Mas o arxiv: 1204.1505 parece dar a impressão de que essa lacuna não é conhecida. o que estou perdendo?
fonte
Respostas:
(Redução da disjunção do conjunto)
fonte
Eu espero que isso ajude.
fonte
O protocolo mais rápido que consigo pensar é alternar a troca de um par adjacente aleatório de elementos, jogando fora coisas que são ignoradas.
Alice [1,10,26,49,50] Bob [2,3,25,49,51]
O par adjacente de Alice é [10,26], então Bob joga fora 25
Alice [1,49,50] Bob [2,3,49,51]
O par adjacente de Bob é [3,49] igual a 49, então pare
fonte