Unbiased bits from sources of weak randomness and probabilistic communication complexity

Abstract

We introduce a general model for physical sources or weak randomness. Loosely speaking, we view physical sources as devices which output strings according to probability distributions in which no single string is too probable. The main question addressed is whether it is possible to extract alrnost unbiased random bits from such "probability bounded" sources. We show that most or the functions can be used to extract almost unbiased and independent bits from the output of any two independent "probability-bounded" sources. The number of extractable bits is within a constant factor of the information theoretic bound. We conclude this paper by establishing further connections between communication complexity and the problem discussed above. This allows us to show that most Boolean functions have linear communication complexity in a very strong sense.