In Andrew Chi-Chih Yao's classic 1979 paper he references "M. O. Rabin and A. C. Yao, in preparation". This is for the result that the bounded-error communication complexity of the equality function EQ$_N$ (whether two integers in the range $0$ to $N-1$ are equal) is $O(\log\log N)$.
- Andrew Chi-Chih Yao, Some Complexity Questions Related to Distributed Computing (Preliminary Report), STOC 1979, pp. 209–213. doi:10.1145/800135.804414
Alexander Razborov's introductory survey on communication complexity proves this result and states "the following beautiful construction [is] usually attributed to Rabin and Yao". The idea is to consider the bit strings as coefficients of a predetermined polynomial $P(x)$; Alice then picks a random integer $q$ from 0 to $p-1$ for some predetermined prime $p \in [3n,6n]$, where $n = \lceil \log N\rceil$, and sends $(q, P(q) \mod p)$ to Bob.
- Alexander Razborov, Communication Complexity, chapter 8 of "An Invitation to Mathematics", pp. 97–117, Springer, 2011. (preprint)
Did the Rabin/Yao paper ever get to be at least a personal communication/draft/sketch in someone else's paper, or is this one of those indications of the "golden era" where giants roamed the earth and didn't always touch ground when stepping from breakthrough to breakthrough?
