Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-055 | 4th September 1998 00:00

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

RSS-Feed




TR98-055
Authors: Luca Trevisan
Publication: 7th September 1998 09:37
Downloads: 1195
Keywords: 


Abstract:

We introduce a new approach to construct extractors -- combinatorial
objects akin to expander graphs that have several applications.
Our approach is based on error correcting codes and on the Nisan-Wigderson
pseudorandom generator. An application of our approach yields a
construction that is simple to describe and analyze,
does not utilize any of the standard techniques used in related results,
and improves or subsumes almost all the previous constructions.


Comment(s):

Comment #1 to TR98-055 | 17th September 1998 14:17

Relativizable pseudorandom generators and extractors Comment on: TR98-055





Comment #1
Authors: Peter Bro Miltersen
Accepted on: 17th September 1998 14:17
Downloads: 1172
Keywords: 


Abstract:

We point out that to see that the Impagliazzo-Wigderson
construction yields an extractor, it is sufficient to
verify that their construction relativizes.




ISSN 1433-8092 | Imprint