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 min-entropy model.
Indeed, the currently studied min-entropy 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 re-interpreted in the currently used terms.
-
Identifying flat distributions as indicators to what happens
on general min-entropy sources (see Section 2.3),
and demonstrating the usefulness of this identification.
In particular, the existence of a two-source extractor
for logarithmic amount of min-entropy (per block) was demonstarted
by a counting argument that was applied to the set of all flat sources
(whereas the set of all possible min-entropy sources is not finite).
-
Showing that two-source extractors yield seeded single-source 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 min-entropy, but the argument extends to the general case.)
-
Proving the existence of two-source extractors for min-entropy
that is at least logarithmic in the block length (see Section 2.4),
and presenting explicit constructions for min-entropy at least half
the block-length (see Section 2.5). Note also that Corollary 11
goes below the bound of half, assuming the Paley Graph Conjecture.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.