Editing Disperser

{{Multiple issues|
{{more citations needed|date=August 2012}}
{{technical|date=January 2014}}
}}

A '''disperser''' is a one-sided [[randomness extractor|extractor]].<ref>{{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}}</ref> Where an extractor requires that every event gets the same [[probability]] under the [[Continuous uniform distribution|uniform distribution]] and the extracted distribution, only the latter is required for a disperser. So for a disperser, an event <math>A \subseteq \{0,1\}^{m}</math> we have:
<math>Pr_{U_{m}}[A] > 1 - \epsilon</math>

'''Definition (Disperser):''' ''A'' <math>(k, \epsilon)</math>''-disperser is a function''

<math>Dis: \{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}</math>

''such that for every distribution'' <math>X</math> ''on'' <math>\{0,1\}^{n}</math> ''with'' <math>H_{\infty}(X) \geq k</math> ''the support of the distribution'' <math>Dis(X,U_{d})</math> ''is of size at least'' <math>(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&nbsp;&minus;&nbsp;''e'')''M'' vertices on the right.

An [[Extractor (mathematics)|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]]

==References==
{{reflist}}

[[Category:Graph families]]


{{Combin-stub}}