<p>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.)</p>

CC BY-SA 3.0
2017-04-19T09:11:50.853Z
2017-04-19T09:11:50.853Z
András Salamon
<p>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)$.</p>

<ul>
<li>Andrew Chi-Chih Yao, <em>Some Complexity Questions Related to Distributed Computing (Preliminary Report)</em>, STOC 1979, pp. 209–213.  doi:<a href="http://dx.doi.org/10.1145/800135.804414">10.1145/800135.804414</a></li>
</ul>

<p>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.</p>

<ul>
<li>Alexander Razborov, <em>Communication Complexity</em>, chapter 8 of "An Invitation to Mathematics", pp. 97–117, Springer, 2011.  (<a href="http://people.cs.uchicago.edu/%7Erazborov/files/cc.pdf">preprint</a>)</li>
</ul>

<p>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?</p>

<ho.history-overview><communication-complexity>
Does Rabin/Yao exist (at least in a form that can be cited)?
András Salamon
# Does Rabin/Yao exist (at least in a form that can be cited)?

(Asked by: username_0 on 2015-01-03)

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](http://dx.doi.org/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](http://people.cs.uchicago.edu/%7Erazborov/files/cc.pdf))

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?

**Tags:** ho.history-overview, communication-complexity

---

## 1 answers

### Answer by username_0 on 2017-04-19. Score: 8 | Accepted answer

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


---

