Rabin / Yao existe (pelo menos de uma forma que possa ser citada)?

40

No clássico artigo de Andrew Chi-Chih Yao, de 1979, ele faz referência a "MO Rabin e AC Yao, em preparação". Isso ocorre pelo resultado de que a complexidade da comunicação de erro limitado da função de igualdade EQ N (se dois inteiros no intervalo de 0 a N - 1 são iguais) é O ( log log N ) .N0N1O(loglogN)

  • Andrew Chi-Chih Yao, algumas questões de complexidade relacionadas à computação distribuída (relatório preliminar) , STOC 1979, pp. 209-213. doi: 10.1145 / 800135.804414

A pesquisa introdutória de Alexander Razborov sobre a complexidade da comunicação comprova esse resultado e declara "a bela construção a seguir [geralmente] é atribuída a Rabin e Yao". A idéia é considerar as cadeias de bits como coeficientes de um polinômio predeterminado P(x) ; Alice então escolhe um número inteiro aleatório q de 0 a p1 para algum número primo predeterminado p[3n,6n] , onde n=logN e envia para Bob .(q,P(q)modp)

  • Alexander Razborov, Complexidade da comunicação , capítulo 8 de "Um convite à matemática", pp. 97-117, Springer, 2011. ( pré-impressão )

O jornal Rabin / Yao chegou a ser pelo menos uma comunicação pessoal / rascunho / esboço no jornal de outra pessoa, ou é uma daquelas indicações da "era dourada" em que os gigantes vagavam pela terra e nem sempre tocavam o chão quando passando de avanço em avanço?

András Salamon
fonte

Respostas:

7

Depois de mais de dois anos, devo assumir que a resposta é "não". (Publicando esta resposta do esboço, para que a pergunta possa ser marcada como respondida.)

András Salamon
fonte