Disperser Explained

A disperser is a one-sided extractor.^[1] 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

A \subseteq \{ 0 , 1 \} ^{m} we have:Pr _{U _{m}} [A] > 1 - \epsilon

Definition (Disperser): A

(k, \epsilon) -disperser is a functionDis: \{ 0 , 1 \} ^{n} x \{ 0 , 1 \} ^{d} → \{ 0 , 1 \} ^{m}

such that for every distribution

X on \{ 0 , 1 \} ^{n} with H _{infty} (X) \geq k the support of the distribution Dis(X,U _{d} ) is of size at least ( 1- \epsilon) 2 ^{m} .

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

Notes and References

1. Ronen. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the EATCS. 2002. 77. 67–95. 2018-04-10.