{{Short description, Bipartite graph with nodes An

(N,M,D,K,\epsilon)

-extractor is a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

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 Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed b ...

to get a node x on the right side is

\epsilon

-close to the uniform distribution in terms of

total variation distance In probability theory, the total variation distance is a distance measure for probability distributions. It is an example of a statistical distance metric, and is sometimes called the statistical distance, statistical difference or variational dist ...

. A disperser is a related graph. An equivalent way to view an extractor is as a bivariate function :

E : \times \rightarrow /math> 

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

bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented a ...

s with min-entropy

\log K

, the distribution

E(X,U_D)

\epsilon

-close to

U_M

, where

U_T

denotes the uniform distribution on

/math>.

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 In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...

from weakly random sources. ''See''

randomness extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent fro ...

. Using the

probabilistic method The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects fr ...

it is easy to show that extractor graphs with really good parameters exist. The challenge is to find explicit or

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

computable examples of such graphs with good parameters. Algorithms that compute extractor (and disperser) graphs have found many applications in

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

References

* Ronen Shaltiel
Recent developments in extractors
- a survey Graph families Pseudorandomness Theoretical computer science