Disperser

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 [math]\displaystyle{ A \subseteq \{0,1\}^{m} }[/math] we have: [math]\displaystyle{ Pr_{U_{m}}[A] \gt 1 - \epsilon }[/math]

Definition (Disperser): A [math]\displaystyle{ (k, \epsilon) }[/math]-disperser is a function

[math]\displaystyle{ Dis: \{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m} }[/math]

such that for every distribution [math]\displaystyle{ X }[/math] on [math]\displaystyle{ \{0,1\}^{n} }[/math] with [math]\displaystyle{ H_{\infty}(X) \geq k }[/math] the support of the distribution [math]\displaystyle{ Dis(X,U_{d}) }[/math] is of size at least [math]\displaystyle{ (1-\epsilon)2^{m} }[/math].

Graph theory

An (N, M, D, K, e)-disperser is a bipartite graph 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.

Other meanings

A disperser is a high-speed mixing device used to disperse or dissolve pigments and other solids into a liquid.

See also

• Expander graph