We give explicit constructions of extractors which work for a source of

any min-entropy on strings of length $n$. The first construction extracts

any constant fraction of the min-entropy using O(log^2 n) additional

random bits. The second extracts all the min-entropy using O(log^3 n)

additional random bits. Both of these constructions use fewer truly

random bits than any previous construction which works for all

min-entropies and extracts a constant fraction of the min-entropy. We

then improve our second construction and show that we can reduce the

entropy loss to 2log(1/epsilon)+O(1) bits, while still using O(log^3 n)

truly random bits (where entropy loss is defined as [(source min-entropy)

+ (# truly random bits used) - (# output bits)], and epsilon is the

statistical difference from uniform achieved). This entropy loss is

optimal up to a constant additive term.

These extractors are obtained by observing that a weaker notion of

"combinatorial design" suffices for the Nisan-Wigderson pseudorandom

generator, which underlies the recent extractor of Trevisan. We give

near-optimal constructions of such "weak designs" which achieve much

better parameters than possible with the notion of designs used by

Nisan-Wigderson and Trevisan.

Most of our results have been independently obtained

by Ran Raz and Omer Reingold.

In this paper, we give explicit constructions of extractors which work for

a source of any min-entropy on strings of length $n$. The first

construction extracts any constant fraction of the min-entropy using

O(log^2 n) additional random bits. The second extracts all the

min-entropy using O(log^3 n) additional random bits. Both of these

constructions use fewer truly random bits than any previous construction

which works for all min-entropies and extracts a constant fraction of the

min-entropy. We then improve our second construction and show that we can

reduce the entropy loss to 2log(1/epsilon)+O(1) bits, while still using

O(log^3 n) truly random bits (where entropy loss is defined as (source

min-entropy) + (# truly random bits used) - (# output bits), and

epsilon is the statistical difference from uniform achieved). This

entropy loss is optimal up to a constant additive term.

These extractors are obtained by observing that a weaker notion of

"combinatorial design" suffices for the Nisan--Wigderson pseudorandom

generator, which underlies the recent extractor of Trevisan. We give

near-optimal constructions of such "weak designs" which achieve much

better parameters than possible with the notion of designs used by

Nisan--Wigderson and Trevisan.

Most of our results have been independently obtained

by Ran Raz and Omer Reingold.

This TR is superseded by ECCC TR99-046 ("Extracting all the

Randomness and Reducing the Error in Trevisan's Extractors," by Ran Raz,

Omer Reingold, and Salil Vadhan).