Misplaced Pages

Disperser

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Disperser" – news · newspapers · books · scholar · JSTOR (August 2012) (Learn how and when to remove this message)
This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (January 2014) (Learn how and when to remove this message)
(Learn how and when to remove this message)

A disperser is a one-sided extractor. 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 A ⊆ { 0 , 1 } m {\displaystyle A\subseteq \{0,1\}^{m}} we have: P r U m [ A ] > 1 − ϵ {\displaystyle Pr_{U_{m}}>1-\epsilon }

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

D i s : { 0 , 1 } n × { 0 , 1 } d → { 0 , 1 } m {\displaystyle Dis:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}}

such that for every distribution X {\displaystyle X} on { 0 , 1 } n {\displaystyle \{0,1\}^{n}} with H ∞ ( X ) ≥ k {\displaystyle H_{\infty }(X)\geq k} the support of the distribution D i s ( X , U d ) {\displaystyle Dis(X,U_{d})} is of size at least ( 1 − ϵ ) 2 m {\displaystyle (1-\epsilon )2^{m}} .

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 − 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

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

See also

References

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


Stub icon

This combinatorics-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: