Complexidade de comunicação de localização de elemento comum de dois subconjuntos

8

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 ?S{1,,n}T{1,,n}|ST|=1ST

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.lognSTO(logn)

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.2/3

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?Ω(n)

Dan Stahlke
fonte
1
"Alice e Bob pode apenas adivinhar usando moedas públicas e abortar se adivinhar errado." Não acho que a definição deles de protocolos de comunicação zero permita que Alice e Bob abortem após adivinhar. Se os dois optarem por responder, eles devem vencer com alta probabilidade. ST
Shitikanth
1
Desculpe pela linguagem desleixada. Para esclarecer, eles escolhem usando moedas públicas. Alice aborta se i S e Bob aborta se i T . Se nenhuma das partes aborta, elas respondem i . Esse tipo de artifício às vezes é chamado de "adivinhação". i{1,,n}iSiTi
Dan Stahlke
Entendo o que você quer dizer agora. No entanto, esse é apenas um protocolo de comunicação zero possível para esse problema. Os autores descrevem outro protocolo que abortaria com probabilidade de apenas . 2O(n)
Shitikanth 17/08/2013
arxiv: 1204.1505 mostra que o custo de qualquer protocolo possível de comunicação zero (ZC) com probabilidade de abortar uniforme (sobre as entradas) é delimitado por quase todas as técnicas conhecidas usadas para diminuir o custo de comunicação com limite. O protocolo que mencionei custou o . logn
Dan Stahlke

Respostas:

5

(Redução da disjunção do conjunto)

S,T[n]|ST|1STXXSTO(logn)

STΩ(n)

Shitikanth
fonte
Sim, claro, obrigado! Eu sabia que a resposta deveria envolver disjunção, mas não conseguia vê-la. Embora, antes de encerrar a pergunta, eu gostaria de ver se alguém comenta a aparente diferença entre comunicação e custo de comunicação zero.
Dan Stahlke
Não sei ao certo o que você quer dizer com custo zero de comunicação. Você pode fornecer um link ou uma referência?
Shitikanth
Atualizei a pergunta com um link para um artigo e também fornecerá a definição para o custo de ZC.
Dan Stahlke
ST|ST|=1|ST|>1
2
Ω(n)
1

EQ(s1,t1)EQ(s2,t2)EQ(sn,tn).
x1y1x2y2xnyn.
A complexidade da comunicação desses dois problemas é equivalente, já que a igualdade pode ser feita a um custo de comunicação aleatório constante.

isi=tiIPIPIPΘ(n)

Eu espero que isso ajude.

Philippe Lamontagne
fonte
-3

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

Chad Brewbaker
fonte