Extractor (matemáticas)

An ${displaystyle (N,M,D,K,epsilon)}$ -extractor es un gráfico bipartito con ${displaystyle N}$ nodos a la izquierda y ${displaystyle M}$ nodos a la derecha tal que cada nodo a la izquierda tiene ${displaystyle D}$ vecinos (a la derecha), que tiene la propiedad agregada que para cualquier subconjunto ${displaystyle A}$ de los vértices izquierdos de tamaño al menos ${displaystyle K}$, la distribución en los vértices correctos obtenidos eligiendo un nodo aleatorio en ${displaystyle A}$ y luego seguir un borde al azar para conseguir un nodo x en el lado derecho es ${displaystyle epsilon }$-cerrar a la distribución uniforme en términos de distancia total de variación.

Un dispersor es un gráfico relacionado.

Una forma equivalente de ver un extractor es como una función bivariada

${displaystyle E:[N]times [D]rightarrow [M]$

de la manera natural. Con esta opinión resulta que la propiedad del extractor es equivalente a: para cualquier fuente de aleatoriedad ${displaystyle X}$ que da ${displaystyle n}$ bits con min-entropía ${displaystyle log K}$, la distribución ${displaystyle E(X,U_{D}}$ es ${displaystyle epsilon }$-Cerca a ${displaystyle U_{M}$, donde ${displaystyle U_{T}$ denota la distribución uniforme sobre ${displaystyle [T]$.

Extractores son interesantes cuando se pueden construir con pequeños ${displaystyle K,D,epsilon }$ relativa a ${displaystyle N}$ y ${displaystyle M}$ es tan cerca ${displaystyle KD}$ (la aleatoriedad total en las fuentes de entrada) como sea posible.

Las funciones de extractor se investigaron originalmente como una forma de extraer la aleatoriedad de fuentes débilmente aleatorias. Ver extractor de aleatoriedad.

Usando el método probabilístico, es fácil mostrar que existen gráficos extractores con parámetros realmente buenos. El desafío es encontrar ejemplos computables en tiempo explícito o polinomial de dichos gráficos con buenos parámetros. Los algoritmos que calculan gráficos extractores (y dispersores) han encontrado muchas aplicaciones en informática.