Disperser

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 we have:

Definition (Disperser): A -disperser is a function

such that for every distribution on with the support of the distribution is of size at least .

Graph theory[edit]

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[edit]

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

See also[edit]

References[edit]

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