en.wikipedia.org

Disperser - Wikipedia

  • ️Tue Apr 10 2018

From Wikipedia, the free encyclopedia

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}}.

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.

A disperser is a high-speed mixing device used to disperse or dissolve pigments and other solids into a liquid.

  1. ^ Shaltiel, Ronen (2002). "Recent developments in explicit constructions of extractors". Bulletin of the EATCS. 77: 67–95. Retrieved 2018-04-10.