World Library  
Flag as Inappropriate
Email this Article

Extractor (mathematics)

Article Id: WHEBN0000009309
Reproduction Date:

Title: Extractor (mathematics)  
Author: World Heritage Encyclopedia
Language: English
Subject: Pseudorandomness, Disperser, List decoding, List of probability topics, Theoretical computer science
Collection: Graph Families, Pseudorandomness, Theoretical Computer Science
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Extractor (mathematics)

An (N,M,D,K,\epsilon) -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 the left vertices of size at least K, the distribution on right vertices obtained by choosing a random node in A and then following a random edge to get a node x on the right side is \epsilon-close to the uniform distribution in terms of total variation distance.

A disperser is a related graph.

An equivalent way to view an extractor is as a bivariate function

E : [N] \times [D] \rightarrow [M]

in the natural way. With this view it turns out that the extractor property is equivalent to: for any source of randomness X that gives n bits with min-entropy \log K, the distribution E(X,U_D) is \epsilon-close to U_M, where U_T denotes the uniform distribution on [T].

Extractors are interesting when they can be constructed with small K,D,\epsilon relative to N and M is as close to KD (the total randomness in the input sources) as possible.

Extractor functions were originally researched as a way to extract randomness from weakly random sources. See randomness extractor.

Using the probabilistic method it is easy to show that extractor graphs with really good parameters exist. The challenge is to find explicit or polynomial time computable examples of such graphs with good parameters. Algorithms that compute extractor (and disperser) graphs have found many applications in computer science.

References

  • Ronen Shaltiel, Recent developments in extractors - a survey
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.