Dispersor

A dispersador es un extractor unilateral. Cuando un extractor requiere que cada evento obtenga la misma probabilidad bajo la distribución uniforme y la distribución extraída, sólo este último es requerido para un dispersor. Así que para un dispersador, un evento A⊆ ⊆ {}0,1}m{displaystyle Asubseteq{0,1} {m}} tenemos: 1-epsilon }" xmlns="http://www.w3.org/1998/Math/MathML">PrUm[A]■1− − ε ε {displaystyle ¿Por qué?1-epsilon " aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/db07f7af85ad63077cb27053d3e712ee7982e5bd" style="vertical-align: -0.838ex; width:16.567ex; height:2.843ex;"/>

Definición (Dispersor): A ()k,ε ε ){displaystyle (k,epsilon)}-El dispersor es una función

Dis:{}0,1}n× × {}0,1}d→ → {}0,1}m{displaystyle Dis:{0,1}n}times ¿Qué?

tal que para cada distribución X{displaystyle X} on {}0,1}n{displaystyle {0,1} {n}} con HJUEGO JUEGO ()X)≥ ≥ k{displaystyle H_{infty}(X)geq k} el apoyo de la distribución Dis()X,Ud){displaystyle Dis(X,U_{d} es de tamaño al menos ()1− − ε ε )2m{displaystyle (1-epsilon)2^{m}.

Teoría de grafos

Un (N, M, D, K, e)-disperser 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, tal que cada subconjunto de K vértices en el lado izquierdo está conectado a más de (1 − e)M vértices en la derecha.

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

Otros significados

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