An (N,M,D,K,e)-Extractor is a bipartite
graph with N
nodes on the left and M nodes on the right such that each node on the left has D neighbors (on the right), which has the added property that
for any subset A of N of size at least K, choosing a random node in A and then following a random
edge brings you to a node x on the right side with probability within e of the uniform distribution.
These graphs are called "extractors" because they can be used to "extract" randomness from weak random sources.
All Wikipedia text
is available under the
terms of the GNU Free Documentation License