Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR98-047 | 10th December 1998 00:00

Extracting All the Randomness from a Weak Random Source Revision of: TR98-047

RSS-Feed




Revision #1
Authors: Salil Vadhan
Accepted on: 10th December 1998 00:00
Downloads: 1322
Keywords: 


Abstract:


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.


Paper:

TR98-047 | 21st August 1998 00:00

Extracting All the Randomness from a Weakly Random Source





TR98-047
Authors: Salil Vadhan
Publication: 24th August 1998 15:27
Downloads: 1403
Keywords: 


Abstract:


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.


Comment(s):

Comment #1 to TR98-047 | 11th May 2001 12:31

Superseded by ECCC TR99-046 Comment on: TR98-047





Comment #1
Authors: Salil Vadhan
Accepted on: 11th May 2001 12:31
Downloads: 619
Keywords: 


Abstract:

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).




ISSN 1433-8092 | Imprint