Czy istnieje Rabin / Yao (przynajmniej w formie, którą można zacytować)?

W klasycznym artykule Andrew Chi-Chiha Yao z 1979 r. Nawiązuje do „MO Rabin i AC Yao w przygotowaniu”. Wynika to z tego, że złożoność komunikacji z błędem ograniczonym funkcji równości EQ (czy dwie liczby całkowite z zakresu od do są równe) wynosi .$_N$$0$$N-1$$O(\log\log N)$

• Andrew Chi-Chih Yao, Niektóre pytania dotyczące złożoności związane z przetwarzaniem rozproszonym (raport wstępny) , STOC 1979, s. 209–213. doi: 10.1145 / 800135.804414

Wstępne badanie Aleksandra Razborowa dotyczące złożoności komunikacji potwierdza ten wynik i stwierdza, że ​​„następującą piękną konstrukcję [zwykle] przypisuje się Rabinowi i Yao”. Chodzi o to, aby traktować ciągi bitów jako współczynniki z góry określonego wielomianu ; Alice następnie wybiera losową liczbę całkowitą od 0 do dla pewnej z góry określonej liczby pierwszej , gdzie , i wysyła (q, P (q) \ mod p) do Boba.$P(x)$$q$$p-1$$p \in [3n,6n]$$n = \lceil \log N\rceil$$(q, P(q) \mod p)$

• Alexander Razborov, Złożoność komunikacji , rozdział 8 „Zaproszenia do matematyki”, s. 97–117, Springer, 2011. ( preprint )

Czy papier Rabin / Yao kiedykolwiek stał się przynajmniej osobistą komunikacją / szkicem / szkicem w czyimś papierze, czy jest to jedna z tych oznak „złotej ery”, w której giganci wędrowali po ziemi i nie zawsze dotykali ziemi, gdy przechodząc od przełomu do przełomu?

Po ponad dwóch latach muszę założyć, że odpowiedź brzmi „nie”. (Opublikowanie tej krótkiej odpowiedzi, aby pytanie można było oznaczyć jako odpowiedź).