Rozptylovač - Disperser

A rozptylovač je jednostranný extraktor.^[1] Kde extraktor vyžaduje, aby každá událost byla stejná pravděpodobnost pod rovnoměrné rozdělení a extrahovaná distribuce, pro dispergátor je vyžadována pouze ta druhá. Takže pro rozptylovač, událost ${displaystyle Asubseteq {0,1} ^ {m}}$ my máme: ${displaystyle Pr_ {U_ {m}} [A]> 1-epsilon}$

Definice (Disperser): A ${displaystyle (k, epsilon)}$ -disperzní je funkce

${displaystyle Dis: {0,1} ^ {n} je {0,1} ^ {d} ightarrow {0,1} ^ {m}}$

takové, že pro každou distribuci ${displaystyle X}$ na ${displaystyle {0,1} ^ {n}}$ s ${displaystyle H_ {infty} (X) geq k}$ podpora distribuce ${displaystyle Dis (X, U_ {d})}$ má velikost minimálně ${displaystyle (1-epsilon) 2 ^ {m}}$ .

Teorie grafů

An (N, M, D, K., E) - rozptyl je bipartitní graf s N vrcholy na levé straně, každý se stupněm D, a M vrcholy na pravé straně, takže každý podmnožina z K. vrcholy na levé straně jsou spojeny s více než (1 -E)M vrcholy vpravo.

An extraktor je související typ grafu, který zaručuje ještě silnější vlastnost; každý (N, M, D, K., E) -extraktor je také (N, M, D, K., E) - rozptyl.

Jiné významy

Dispergátor je vysokorychlostní směšovací zařízení používané k dispergování nebo rozpuštění pigmentů a jiných pevných látek na kapalinu.

Viz také

Expander graf

Reference

^ Shaltiel, Ronen (2002). „Poslední vývoj v explicitních konstrukcích extraktorů“. Bulletin EATCS. 77: 67–95. Citováno 2018-04-10.

Tento kombinatorika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Shaltiel, Ronen (2002). „Poslední vývoj v explicitních konstrukcích extraktorů“. Bulletin EATCS. 77: 67–95. Citováno 2018-04-10.

[1]