Un extractor es un gráfico bipartito con nodos a la izquierda y nodos a la derecha, de modo que cada nodo de 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 y luego seguir un borde aleatorio para obtener un nodo x en el lado derecho está 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. Desde este punto de vista, resulta que la propiedad del extractor es equivalente a: para cualquier fuente de aleatoriedad que proporcione bits con entropía mínima , la distribución es cercana a , donde denota la distribución uniforme en .
Los extractores son interesantes cuando se pueden construir con una relación pequeña y lo más cercana 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 débilmente aleatorias. Ver extractor de aleatoriedad .
Utilizando 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 en tiempo explícito o polinomial de tales gráficos con buenos parámetros. Los algoritmos que calculan gráficos extractores (y dispersores) han encontrado muchas aplicaciones en informática .
![{\displaystyle E:[N]\times [D]\rightarrow [M]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6df376d7050374d085cfa8e6b7b86dcd7a4cf5f)
![{\displaystyle [T]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2c8afd013f811776289b0d3f804a430888eccc)
