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 .
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 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 .
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.
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 .
![{\displaystyle E:[N]\times [D]\rightarrow [M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6df376d7050374d085cfa8e6b7b86dcd7a4cf5f)
![{\estilo de visualización [T]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2c8afd013f811776289b0d3f804a430888eccc)
