Существует ли Рабин / Яо (по крайней мере, в той форме, которую можно привести)?

40

В классической работе Эндрю Чи-Чжа Яо 1979 года он упоминает "М.О. Рабин и А.С. Яо, в процессе подготовки". Это связано с тем, что сложность связи с ограниченной ошибкой функции равенства EQ (два целых числа в диапазоне от до 0 N - 1 O ( журнал регистрации N )N0N1 ) равна .O(loglogN)

  • Эндрю Чи-Чи Яо, Некоторые вопросы сложности, связанные с распределенными вычислениями (предварительный отчет) , STOC 1979, стр. 209–213. doi: 10.1145 / 800135.804414

Вступительное исследование Александра Разборова о сложности общения подтверждает этот результат и утверждает, что «следующая красивая конструкция обычно приписывается Рабину и Яо». Идея состоит в том, чтобы рассматривать битовые строки как коэффициенты заранее определенного многочлена ; Затем Алиса выбирает случайное целое число от 0 до для некоторого заранее определенного простого числа , гдеP(x)qp1p[3n,6n]n=logN , и отправляет (q,P(q)modp) Бобу

  • Александр Разборов, Коммуникационная сложность , глава 8 «Приглашение к математике», с. 97–117, Springer, 2011. ( препринт )

Была ли когда-нибудь бумага Рабина / Яо хотя бы личным сообщением / черновиком / эскизом в чужой газете, или это одно из тех указаний на «золотую эру», когда гиганты бродили по земле и не всегда касались земли, когда переходить от прорыва к прорыву?

Андраш Саламон
источник

Ответы:

7

После более чем двух лет я должен предположить, что ответ «нет». (Разместите ответ на этот вопрос, чтобы вопрос можно было пометить как ответивший.)

Андраш Саламон
источник