Extractor (matemáticas)

Un extractor es un gráfico bipartito con nodos a la izquierda y nodos a la derecha de modo que cada nodo a la izquierda tiene vecinos (a la derecha), que tiene la propiedad adicional de que para cualquier subconjunto de los vértices izquierdos de tamaño al menos , la distribución en los vértices derechos obtenida al elegir un nodo aleatorio en y luego seguir un borde aleatorio para obtener un nodo x en el lado derecho es -cercana a la distribución uniforme en términos de distancia de variación total . ${\displaystyle (N,M,D,K,\epsilon)}$${\estilo de visualización N}$${\estilo de visualización M}$${\estilo de visualización D}$${\estilo de visualización A}$${\estilo de visualización K}$${\estilo de visualización A}$${\displaystyle \épsilon}$

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 forma natural. Con esta visión resulta que la propiedad del extractor es equivalente a: para cualquier fuente de aleatoriedad que dé bits con min-entropía , la distribución es -cercana a , donde denota la distribución uniforme en . ${\estilo de visualización X}$${\estilo de visualización n}$ ${\estilo de visualización \log K}$${\displaystyle E(X,U_{D})}$${\displaystyle \épsilon}$${\displaystyle U_{M}}$$Estilo de visualización U_{T}}$${\estilo de visualización [T]}$

Los extractores son interesantes cuando se pueden construir con valores relativos pequeños y lo más cercanos posible a la aleatoriedad total en las fuentes de entrada. ${\displaystyle K,D,\épsilon}$${\estilo de visualización N}$${\estilo de visualización M}$${\estilo de visualización KD}$

Las funciones de extracción se investigaron originalmente como una forma de extraer aleatoriedad de fuentes poco aleatorias. Ver extractor de aleatoriedad .

Utilizando el método probabilístico es fácil demostrar que existen grafos extractores con parámetros realmente buenos. El desafío es encontrar ejemplos explícitos o computables en tiempo polinomial de tales grafos con buenos parámetros. Los algoritmos que calculan grafos extractores (y dispersores) han encontrado muchas aplicaciones en la ciencia informática .

• Ronen Shaltiel, Desarrollos recientes en extractores: una encuesta