ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > HARDNESS VERSUS RANDOMNESS:
Reports tagged with hardness versus randomness:
TR00-009 | 21st February 2000
Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

Extractors and pseudo-random generators with optimal seed length

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



ISSN 1433-8092 | Imprint