Testando positividade em vez de igualdade

14

Alice e Bob têm strings de n bits e querem descobrir se são iguais enquanto fazem pouca comunicação. A solução aleatória padrão é tratar as seqüências de n bits como polinômios de grau n e depois avaliar os polinômios sobre alguns elementos escolhidos aleatoriamente em um campo de tamanho maior que n . Isso requer comunicação O(log|F|) .

Suponha, em vez disso, que fixemos uma ordem lexicográfica sobre as seqüências de caracteres e desejemos determinar qual sequência é "maior", o que equivale a encontrar o bit mais à esquerda onde as sequências diferem.

Existe um protocolo aleatório semelhante para fazer isso ou um limite inferior conhecido? Isso parece estar relacionado ao teste de positividade de polinômios.

ps Embora a ordem lexicográfica pareça a mais óbvia, eu estou bem com outras ordens: para o propósito em que estou interessado, tudo o que precisamos é de alguma ordem.

Suresh Venkat
fonte
1
Eu pensei que a solução aleatória padrão era escolher uma combinação linear aleatória dos bits e apenas enviar a paridade resultante, que requer apenas comunicação ? O(1)
Joshua Grochow
@ JoshuaGrochow Acho que depende da natureza da aleatoriedade - pública ou privada. O protocolo que você menciona usa aleatoriedade pública.
Sasho Nikolov
1
Para comparação, talvez valha a pena mencionar que a complexidade determinística é , portanto o protocolo trivial é ideal. Isso fornece uma boa lacuna exponencial entre soluções determinísticas / exatas e randomizadas, mostrando que (pelo menos na complexidade da comunicação), a aleatoriedade realmente pode ajudar. n+1
András Salamon
1
Um sim. Quanta comunicação é necessária para um algoritmo que nunca fornece a resposta errada e, para todos os pares de entrada, fornece MAYBE a esse par de entradas com probabilidade no máximo 1/2?
1
Talvez valha a pena mencionar que a complexidade da comunicação em torno de é maior que Ω ( n 1 / k k - 2 ) em particular, ou seja, é linear para k = 1 , consulte arxiv.org/abs/cs/0309033 . É um papel nice :)kΩ(n1/kk-2)k=1
Marc Bury

Respostas:

11

Isso é conhecido como problema maior que a complexidade da comunicação. Existe um algoritmo com complexidade de comunicação (Exercício 3.18 no livro Nisan-Kushilevitz).O(registron)

Edit: O algoritmo é devido ao Nisan (página 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf

Ele usa a abordagem sugerida por @Sasho Nikolov abaixo --- executando uma pesquisa binária usando testes de igualdade com erro constante para fazer as comparações. Isso pode ser feito com consultas usando o "algoritmo de pesquisa binária barulhenta" de Feige, Peleg, Raghavan e Upfal: http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdfO(registron)

Para obter um protocolo de aleatoriedade privado (não explícito), é possível aplicar o resultado de Newman: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf

Grigory Yaroslavtsev
fonte
5
registronO(1)
2
O(registronregistroregistron)O(1/registron)O(registroregistron)
2
@SashoNikolov Ok, acho que algo assim pode ser usado como uma "pesquisa binária barulhenta", que tolera uma fração constante de erros, para que possamos usar a probabilidade de erro constante nos testes de igualdade: dl.acm.org/citation.cfm? id = 167129
Grigory Yaroslavtsev
1
verdade. Eu quis dizer pesquisa binária em que cada comparação pode dar o resultado errado com pequena probabilidade constante. Acho que este artigo fornece o resultado necessário, por exemplo: dl.acm.org/citation.cfm?id=100230
Sasho Nikolov
Movido a discussão para a resposta.
Grigory Yaroslavtsev