Un - el extractor es un gráfico bipartito con nodos de la izquierda y nodos de la derecha, de modo que cada nodo de la izquierda tiene vecinos (a la derecha), que tiene la propiedad añadida 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 siguiendo un borde aleatorio para obtener un nodo x en el lado derecho es-cerca de la distribución uniforme en términos de distancia de variación total .
Un dispersor es un gráfico relacionado.
Una forma equivalente de ver un extractor es como una función bivariada
de forma natural. Con esta vista, resulta que la propiedad del extractor es equivalente a: para cualquier fuente de aleatoriedad eso da bits con min-entropía , la distribución es -cerca de , dónde denota la distribución uniforme en .
Los extractores son interesantes cuando se pueden construir con pequeños relativo a y está tan cerca de (la aleatoriedad total en las fuentes de entrada) como sea posible.
Las funciones de extracción se investigaron originalmente como una forma de extraer aleatoriedad de fuentes débilmente aleatorias. Ver extractor de aleatoriedad .
Usando el método probabilístico es fácil demostrar que existen gráficos extractores con parámetros realmente buenos. El desafío es encontrar ejemplos computables explícitos o polinomiales de tales gráficos con buenos parámetros. Los algoritmos que calculan gráficos extractores (y dispersores) han encontrado muchas aplicaciones en la informática .
Referencias
- Ronen Shaltiel, Desarrollos recientes en extractores : una encuesta