:"This article is about the extractor in mathematics, for other usage of this word see:
An -extractor is a
bipartite graphwith nodes on the left and nodes on the right such that each node on the left has neighbors (on the right), which has the added property thatfor any subset of the left vertices of size at least , the distribution on right vertices obtained by choosing a random node in and then following a random edge to get a node x on the right side is -close to the uniform distributionin terms of total variation distance.
disperseris a related graph.
An equivalent way to view an extractor is as a bivariate function
in the natural way. With this view it turns out that the extractor property is equivalent to: for any source of randomness that gives
bits with min-entropy, the distribution is -close to , where denotes the uniform distribution on .
Extractors are interesting when they can be constructed with small relative to and is as close to (the total randomness in the input sources) as possible.
Extractor functions were originally researched as a way to "extract"
randomnessfrom weakly random sources. "See" randomness extractor.
probabilistic methodit is easy to show that extractor graphs with really good parameters exist. The challenge is to find explicit or polynomial timecomputable examples of such graphs with good parameters. Algorithms that compute extractor (and disperser) graphs have found many applications in computer science.
* Ronen Shaltiel, [http://www.cs.haifa.ac.il/~ronen/online_papers/survey.ps Recent developments in extractors] - a survey
Wikimedia Foundation. 2010.