Unbiased Bits From Sources of Weak Randomness and Probabilistic Communication Complexity

Webpage for a paper by Benny Chor and Oded Goldreich


A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g., the Santha and Vazirani model). The sources considered output strings according to probability distributions in which no single string is too probable. The new model provides a fruitful viewpoint on problems studied previously as: This work first appeared in the 25th FOCS, 1984.

A later perspective (2006)

In retrospect, the most important contributions of this work are:

Material available on-line

Back to either Oded Goldreich's homepage. or general list of papers.