Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-009 | 21st February 2000 00:00

Extractors and pseudo-random generators with optimal seed length


Authors: Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson
Publication: 22nd February 2000 09:19
Downloads: 3949


We give the first construction of a pseudo-random generator with
optimal seed length that uses (essentially) arbitrary hardness.
It builds on the novel recursive use of the NW-generator in
a previous paper by the same authors, which produced many optimal
generators one of which was pseudo-random. This is achieved in two
stages - first significantly reducing the number of candidate generators,
and then efficiently combining them into one.

We also give the first construction of an extractor with optimal seed
length, that can handle sub-polynomial entropy levels.
It builds on the fundamental connection between extractors and
pseudo-random generators discovered by Trevisan, combined
with construction above. Moreover, using Kolmogorov Complexity rather
than circuit size in the analysis gives super-polynomial savings for
our construction, and renders our extractors better than known for all
entropy levels.

ISSN 1433-8092 | Imprint