Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources

The semi-random source, defined by Sántha and Vazirani, is a general mathematical mode for imperfect and correlated sources of randomness (physical sources such as noise dicdes). In this paper an algorithm is presented which efficiently generates “high quality” random sequences (quasirandom bit-sequences) from two independent semi-random sources. The general problem of extracting “high quality” bits is shown to be related to communication complexity theory, leading to a definition of strong communication complexity of a boolean function. A hierarchy theorem for strong communication complexity classes is proved; this allows the previous algorithm to be generalized to one that can generate quasi-random sequences from two communicating semi-random sources This research was supported in part by an IBM Doctoral Felloswhip and by NSF Grant MCS 82-04506.