# Extractor

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.