Randomness extractors and their many guises
Salil Vadhan · 2003
Since its introduction by Nisan and Zuckerman at STOC '93 (1996) nearly a decade ago, the notion of a randomness extractor has proven to be a fundamental and powerful one. Extractors and their variants have found widespread application in a variety of areas, including pseudorandomness and derandomization, combinatorics, cryptography, data structures, and computational complexity. Equally striking has been a sequence of discoveries showing that, under different interpretations, extractors are close relatives of a number of other important objects, such as expander graphs, hash functions, error-correcting codes, pseudorandom generators, and sampling algorithms. Through these connections, extractors have unified the study of these objects and have led to new and improved constructions of each. We give an introduction to the study of extractors. The article is built around the connections between extractors and the other objects mentioned above. Within the context of these connections, we hope to convey an understanding of the definition of extractors, some intuition for how they are constructed, and a glimpse of their use in applications.