Unbiased Bits From Sources of Weak
Randomness and Probabilistic Communication Complexity
Webpage for a paper by Benny Chor and Oded Goldreich
Abstract
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:
 Extracting almost perfect bits from sources of
weak randomness: The question of possibility as well as the
question of efficiency of such extraction schemes are addressed.
 Probabilistic Communication Complexity:
it is shown that most functions have linear communication complexity
in a very strong probabilistic sense.
 Robustness of BPP with respect to sources of weak randomness
(generalizing a result of Vazirani and Vazirani).
This work first appeared in the 25th FOCS, 1984.
A later perspective (2006)
In retrospect, the most important contributions of this work are:

Putting forward the model of probability bounded distributions
(see Section 2.1),
which is currently known as the minentropy model.
Indeed, the currently studied minentropy sources correspond
to a single block in the sources defined in this work, and
consequently efficiency is measured with respect to the block length
and not with respect to the number of blocks. The results of this
paper can be easily reinterpreted in the currently used terms.

Identifying flat distributions as indicators to what happens
on general minentropy sources (see Section 2.3),
and demonstrating the usefulness of this identification.
In particular, the existence of a twosource extractor
for logarithmic amount of minentropy (per block) was demonstarted
by a counting argument that was applied to the set of all flat sources
(whereas the set of all possible minentropy sources is not finite).

Showing that twosource extractors yield seeded singlesource extractors
(see beginning of Section 5).
Specifically, the second source is replaced by the seed
(or is rather emulated by the seed).
(Indeed, Lemma 27 refers to a special case where the second source has
almost maximum minentropy, but the argument extends to the general case.)

Proving the existence of twosource extractors for minentropy
that is at least logarithmic in the block length (see Section 2.4),
and presenting explicit constructions for minentropy at least half
the blocklength (see Section 2.5). Note also that Corollary 11
goes below the bound of half, assuming the Paley Graph Conjecture.
Material available online
Back to
either Oded Goldreich's homepage.
or general list of papers.