Apakah Rabin / Yao ada (setidaknya dalam bentuk yang dapat dikutip)?

Dalam makalah klasik 1979 karya Andrew Chi-Chih Yao ia merujuk "MO Rabin dan AC Yao, dalam persiapan". Ini adalah untuk hasil bahwa kompleksitas komunikasi kesalahan terbatas dari fungsi kesetaraan EQ N (apakah dua bilangan bulat dalam kisaran 0 hingga N - 1 sama) adalah O ( log log N ) .$_N$$0$$N-1$$O(\log\log N)$

• Andrew Chi-Chih Yao, Beberapa Pertanyaan Kompleksitas Terkait dengan Komputer Terdistribusi (Laporan Awal) , STOC 1979, hlm. 209–213. doi: 10.1145 / 800135.804414

Survei pengantar Alexander Razborov pada kompleksitas komunikasi membuktikan hasil ini dan menyatakan "konstruksi indah berikut ini biasanya dikaitkan dengan Rabin dan Yao". Idenya adalah untuk mempertimbangkan string bit sebagai koefisien dari polinomial telah ditentukan ; Alice kemudian memilih integer acak q dari 0 ke p - 1 untuk beberapa prima yang telah ditentukan p ∈ [ 3 n , 6 n ] , di mana n = ⌈ log N ⌉ , dan mengirimkan ke Bob .$P(x)$$q$$p-1$$p \in [3n,6n]$$n = \lceil \log N\rceil$$(q, P(q) \mod p)$

• Alexander Razborov, Kompleksitas Komunikasi , bab 8 "An Invitation to Mathematics", hlm. 97–117, Springer, 2011. ( pracetak )

Apakah kertas Rabin / Yao pernah menjadi setidaknya komunikasi pribadi / draft / sketsa di kertas orang lain, atau apakah ini salah satu dari indikasi "era emas" di mana para raksasa menjelajahi bumi dan tidak selalu menyentuh tanah ketika melangkah dari terobosan ke terobosan?

Setelah lebih dari dua tahun, saya harus menganggap jawabannya adalah "tidak". (Posting jawaban rintisan ini sehingga pertanyaan dapat ditandai sebagai dijawab.)