Extractors and pseudorandom generators

@article{citeulike:812812, abstract = {We introduce a new approach to constructing extractors. Extractors are algorithms that transform a \&quote;weakly random\&quote; distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, and tend to be very difficult to obtain.We demonstrate an unsuspected connection between extractors and pseudorandom generators. In fact, we show that every pseudorandom generator of a certain kind is an extractor.A pseudorandom generator construction due to Impagliazzo and Wigderson, once reinterpreted via our connection, is already an extractor that beats most known constructions and solves an important open question. We also show that, using the simpler Nisan--Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are simple and admit a short self-contained description.}, address = {New York, NY, USA}, author = {Trevisan, Luca }, citeulike-article-id = {812812}, doi = {10.1145/502090.502099}, issn = {0004-5411}, journal = {J. ACM}, keywords = {extractors, pseudo-randomness}, month = {July}, number = {4}, pages = {860--879}, posted-at = {2006-08-22 16:31:27}, priority = {4}, publisher = {ACM Press}, title = {Extractors and pseudorandom generators}, url = {http://portal.acm.org/citation.cfm?id=502099}, volume = {48}, year = {2001} }

TY - JOUR ID - citeulike:812812 L3 - citeulike-article-id:812812 TI - Extractors and pseudorandom generators JF - J. ACM VL - 48 IS - 4 SP - 860 EP - 879 AD - New York, NY, USA PB - ACM Press SN - 0004-5411 N2 - We introduce a new approach to constructing extractors. Extractors are algorithms that transform a &quote;weakly random&quote; distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, and tend to be very difficult to obtain.We demonstrate an unsuspected connection between extractors and pseudorandom generators. In fact, we show that every pseudorandom generator of a certain kind is an extractor.A pseudorandom generator construction due to Impagliazzo and Wigderson, once reinterpreted via our connection, is already an extractor that beats most known constructions and solves an important open question. We also show that, using the simpler Nisan--Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are simple and admit a short self-contained description. KW - extractors KW - pseudo-randomness AU - Trevisan, Luca PY - 2001/07// UR - http://portal.acm.org/citation.cfm?id=502099 ER -