Dispersor

Un dispersor es un extractor unilateral . ^[1] Cuando un extractor requiere que cada evento tenga la misma probabilidad bajo la distribución uniforme y la distribución extraída, solo se requiere esta última para un dispersor. Entonces, para un dispersor, un evento tenemos: ${\displaystyle A\subseteq \{0,1\}^{m}}$ ${\displaystyle Pr_{U_{m}}[A]>1-\epsilon }$

Definición (dispersor): un dispersor es una función ${\displaystyle (k,\epsilon )}$

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

de modo que para cada distribución con el apoyo de la distribución sea de tamaño al menos . ${\displaystyle X}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle H_{\infty }(X)\geq k}$ ${\displaystyle Dis(X,U_{d})}$ ${\displaystyle (1-\epsilon )2^{m}}$

Teoría de grafos

Un ( N , M , D , K , e )-dispersor es un gráfico bipartito con N vértices en el lado izquierdo, cada uno con grado D y M vértices en el lado derecho, de modo que cada subconjunto de K vértices en el lado izquierdo está conectado a más de (1 −  e ) M vértices a la derecha.

Un extractor es un tipo de gráfico relacionado que garantiza una propiedad aún más sólida; cada extractor ( N , M , D , K , e ) es también un dispersor ( N , M , D , K , e ) .

Otros significados

Un dispersor es un dispositivo mezclador de alta velocidad que se utiliza para dispersar o disolver pigmentos y otros sólidos en un líquido.

Ver también

• Gráfico de expansión

Referencias

1. Shaltiel, Ronen (2002). "Desarrollos recientes en construcciones explícitas de extractores". Boletín de la EATCS . 77 : 67–95 . Consultado el 10 de abril de 2018 .