39
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

After more than two years, I have to assume the answer is "no". (Posting this stub answer so the question can be marked as answered.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.