Disperser

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 function

$Dis:\{0,1\}^{{n}}\times \{0,1\}^{{d}}\rightarrow \{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.

References

↑ Ronen Shaltiel. Recent developments in explicit construction of extractors. P. 7.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Disperser

Graph theory

Other meanings

See also

References