“Disperser”的意思、由来-开放百科全书

词条

Disperser

释义

Graph theory
Other meanings
See also
References

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:

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

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.

References

1. ^{{cite journal|first=Ronen|last=Shaltiel|title=Recent developments in explicit constructions of extractors|journal=Bulletin of the EATCS|year=2002|volume=77|pages=67–95|url=https://cs.haifa.ac.il/~ronen/online_papers/survey.ps|accessdate=2018-04-10}}

1 : Graph families

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Graph theory

Other meanings

See also

References