Disperser

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

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

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

such that for every distribution X on {0,1}ⁿ with $H_{\infty}(X) \geq k$ the support of the distribution Dis(X,U_d) is of size at least $(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

• Expander graph

References

1. ^ Ronen Shaltiel. Recent developments in explicit construction of extractors. P. 7.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Graph families Combinatorics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Data warehouse Devonian Look at other dictionaries: disperser — [ dispɛrse ] v. tr. <conjug. : 1> • v. 1450; lat. dispersus, p. p. de dispergere « répandre çà et là » 1 ♦ Jeter, répandre çà et là. ⇒ disséminer, éparpiller, parsemer, répandre, semer. Disperser les débris de qqch. « Ce grand vent aura… …   Encyclopédie Universelle disperser — DISPERSER. v. a. Répandre, jeter çà et là. Disperser de l argent, des présens, etc. f♛/b] Il se dit aussi Des personnes, et signifie, Les séparer, en les mettant, en les envoyant en divers lieux. Disperser des troupes, des soldats. [b]f♛/b] Il… …   Dictionnaire de l'Académie Française 1798 disperser — DISPERSER. v. a. Respandre, jetter çà & là. Disperser de l argent, des presens, &c. Il se dit aussi Des personnes, & signifie, Les separer, en les mettant, en les envoyant en divers lieux. Disperser des troupes, des soldats. les Juifs furent… …   Dictionnaire de l'Académie française Disperser — Dis*pers er, n. One that disperses. [1913 Webster] …   The Collaborative International Dictionary of English disperser — (di spèr sé) v. a. 1°   Jeter, pousser çà et là. Disperser les débris de quelque chose.    Détruire en jetant çà et là les débris. •   Ils disperseront vos cabanes, ils se jetteront sur vos troupeaux, RAYNAL Hist. phil. II, 18. 2°   Répartir çà… …   Dictionnaire de la Langue Française d'Émile Littré DISPERSER — v. a. Répandre, jeter çà et là. Disperser les débris de quelque chose. Disperser de l argent, des pièces de monnaie, etc.   Il signifie aussi, Séparer des personnes ou des choses qui formaient un assemblage, et les mettre, les envoyer, les porter …   Dictionnaire de l'Academie Francaise, 7eme edition (1835) DISPERSER — v. tr. Répandre, jeter çà et là. Disperser les débris de quelque chose. La boîte tomba et les objets qu’elle contenait se dispersèrent de tous côtés. Il signifie aussi Séparer des personnes ou des choses qui formaient un assemblage et les mettre …   Dictionnaire de l'Academie Francaise, 8eme edition (1935) disperser — vt. , éparpiller, répandre, mettre en désordre ; épancher ; mettre en fuite : épaslyî (Leschaux), éspars(a)lyî (Albanais.001, Annecy | Thônes), épasklyî (Compôte Bauges) ; épatushé (Arvillard.228) / î (001) ; éwâ (001) ; disparsâ (Aix, KER.),… …   Dictionnaire Français-Savoyard disperser — dispergentas statusas T sritis chemija apibrėžtis Medžiaga, pagreitinanti dispergavimą. atitikmenys: angl. dispergator; disperser; dispersing agent rus. диспергатор; диспергирующий агент …   Chemijos terminų aiškinamasis žodynas disperser — disperse ► VERB 1) go or distribute in different directions or over a wide area. 2) thin out and eventually disappear. 3) Physics divide (light) into constituents of different wavelengths. DERIVATIVES dispersal noun disperser noun dispersible… …   English terms dictionary 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”