Disperser

Summary

(Learn how and when to remove this template message)

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

Definition (Disperser): A ${\displaystyle (k,\epsilon )}$-disperser is a function

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

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

Graph theory edit

Other meanings edit

See also edit

References edit