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

40

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 .N0N1O(loglogN)

  • 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)qp1p[3n,6n]n=logN(q,P(q)modp)

  • 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?

András Salamon
źródło

Odpowiedzi:

7

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ź).

András Salamon
źródło