Randomness Extraction: A Survey

Randomness Extraction: A Survey - David Zuckerman

David Zuckerman
University of Texas at Austin; Institute for Advanced Study
February 7, 2012
A randomness extractor is an efficient algorithm which extracts high-quality randomness from a low-quality random source. Randomness extractors have important applications in a wide variety of areas, including pseudorandomness, cryptography, expander graphs, coding theory, and inapproximability. In this talk, we survey the field of randomness extraction and discuss connections with other areas.