Encyclopedia > Extractor

  Article Content

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Northwest Harbor, New York

... average family size is 3.04. In the town the population is spread out with 25.2% under the age of 18, 4.8% from 18 to 24, 27.3% from 25 to 44, 28.7% from 45 to 64, and ...

 
 
 
This page was created in 40.9 ms