Disperser

{{Multiple issues|

{{more citations needed|date=August 2012}}

{{technical|date=January 2014}}

}}

A disperser is a one-sided extractor.{{cite journal|first=Ronen|last=Shaltiel|title=Recent developments in explicit constructions of extractors|journal=Bulletin of the EATCS|year=2002|volume=77|pages=67–95|url=https://cs.haifa.ac.il/~ronen/online_papers/survey.ps|access-date=2018-04-10}} 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\; \backslash subseteq\; \backslash \{0,1\backslash \}^\{m\}$ we have:

$Pr\_\{U\_\{m\}\}[A]\; >\; 1\; -\; \backslash epsilon$

Definition (Disperser): A $(k,\; \backslash epsilon)$-disperser is a function

$Dis:\; \backslash \{0,1\backslash \}^\{n\}\backslash times\; \backslash \{0,1\backslash \}^\{d\}\backslash rightarrow\; \backslash \{0,1\backslash \}^\{m\}$

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