Disperser
   HOME

TheInfoList



Click Here for Items Related To - Disperser
OR:
Disperser on:   [Wikipedia]   [Google]   [Amazon]

A disperser is a one-sided extractor. Where an extractor requires that every event gets the same
probability Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
under the uniform distribution and the extracted distribution, only the latter is required for a disperser. So for a disperser, an event A \subseteq \^ we have: Pr_ > 1 - \epsilon Definition (Disperser): ''A'' (k, \epsilon)''-disperser is a function'' Dis: \^\times \^\rightarrow \^ ''such that for every distribution'' X ''on'' \^ ''with'' H_(X) \geq k ''the support of the distribution'' Dis(X,U_) ''is of size at least'' (1-\epsilon)2^.


Graph theory

An (''N'', ''M'', ''D'', ''K'', ''e'')-disperser is a
bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
with ''N'' vertices on the left side, each with degree ''D'', and ''M'' vertices on the right side, such that every
subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
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 In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several appli ...


References

Graph families {{Combin-stub