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 the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
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 mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
with ''N'' vertices on the left side, each with degree ''D'', and ''M'' vertices on the right side, such that every
subset In mathematics, 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 are ...
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 applica ...


References

Graph families {{Combin-stub