Disperser
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) (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 we have:
![Pr_{{U_{{m}}}}[A]>1-\epsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/db07f7af85ad63077cb27053d3e712ee7982e5bd)
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]
- ^ Shaltiel, Ronen (2002). "Recent developments in explicit constructions of extractors". Bulletin of the EATCS. 77: 67–95. Retrieved 2018-04-10.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |
No comments:
Post a Comment