Disperser
Encyclopedia
A disperser is a one-sided extractor
. Where an extractor requires that every event gets the same probability
under the uniform distribution and the extracted distribution, only the latter is required for a disperser. So for a disperser, an event
we have:
Definition (Disperser): A
-disperser is a function
such that for every distribution
on 
with 
the support of the distribution 
is of size at least 
.
with N vertices on the left side, each with degree D, and M vertices on the right side, such that every subset
of K vertices on the left side is connected to more than (1 − e)M vertices on the right.
An extractor is a related type of graph that guarantees an even stronger property; every (N, M, D, K, e)-extractor is also an (N, M, D, K, e)-disperser.
Randomness extractor
A randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source , generates a random output that is shorter, but uniformly distributed...
. Where an extractor requires that every event gets the same probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
under the uniform distribution and the extracted distribution, only the latter is required for a disperser. So for a disperser, an event
we have:Definition (Disperser): A
-disperser is a functionsuch that for every distribution
on with the support of the distribution is of size at least .Graph theory
An (N, M, D, K, e)-disperser is a bipartite graphBipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
with N vertices on the left side, each with degree D, and M vertices on the right side, such that every subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of K vertices on the left side is connected to more than (1 − e)M vertices on the right.
An extractor is a related type of graph that guarantees an even stronger property; every (N, M, D, K, e)-extractor is also an (N, M, D, K, e)-disperser.