Luca Trevisan mostró cuántas construcciones de generadores pseudoaleatorios pueden considerarse, de hecho, construcciones extractoras:
http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf
¿Hay una conversación significativa? Es decir, ¿pueden considerarse las construcciones "naturales" de extractores como construcciones de generadores pseudoaleatorios (PRG)?
Las construcciones de extractor parecen corresponder a distribuciones sobre PRG (de modo que cualquier distintivo no logre distinguir para casi todos ellos). ¿Hay aplicaciones conocidas para esto?
fuente
Salil Vadhan me escribió que la respuesta a mi pregunta es conocida y que los PRG son equivalentes a los extractores.
Citando a él:
"Vea la Propuesta 21 y la discusión que sigue en mi encuesta http://people.seas.harvard.edu/~salil/research/unified-icm.pdf (Hay un error tipográfico -" amplificador de dureza de caja negra "debería ser" negro -box construcción PRG ")
Dice que los extractores son equivalentes a las construcciones de PRG de caja negra donde solo le importa la cantidad de consejos, y no el tiempo de ejecución, en la reducción. Pedir tiempo de ejecución limitado equivale a pedir extractores con "decodificación de lista local".
fuente
Hay un buen artículo de Chris Umans sobre el análogo de esta pregunta para los dispersores: http://www.cs.caltech.edu/~umans/papers/U05-final.pdf
Él muestra que los dispersores que tienen un procedimiento de reconstrucción en tiempo polinómico, pero no necesariamente la propiedad de decodificación local, implican la existencia de generadores de conjuntos de golpe.
Aquí hay otra forma de verlo: los extractores se pueden ver como códigos recuperables de la lista (que es una variante más fuerte de los códigos decodificables de la lista), y los PRG de recuadro negro se pueden ver de los códigos recuperables de la lista local . Los dispersores pueden ser vistos como códigos de lista recuperable para error cero. Lo que Chris muestra es que un código de recuperación de lista para error cero que tiene un procedimiento de recuperación de lista de tiempo polinómico implica la existencia de un código de recuperación de lista con un procedimiento de recuperación de lista local .
fuente