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 ) .
- 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 ; Alice então escolhe um número inteiro aleatório de 0 a para algum número primo predeterminado , onde e envia para Bob .
- 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?
fonte