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 .
- 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.
- 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?
źródło