¿Una comparación de extractores en términos de compensaciones entre tiempo, aleatoriedad y espacio?

21

¿Existe una buena encuesta que compare diferentes extractores, concentradores y superconcentradores y exponga los mejores métodos en términos de compensación entre aleatoriedad, tiempo y espacio?

reference-request randomness derandomization Suresh Venkat
fuente
1
Hola Suresh, no creo que los extractores y (super) concentradores sean comparables. ¿Quizás leí mal la pregunta, y quiso decir comparar los algoritmos de construcción? Los parámetros para los (super) concentradores que nos interesan son sus profundidades y tamaños, no "aleatoriedad, tiempo y espacio". [El trabajo de Radhakrishnan y Ta-shma] [1] tiene una tabla que muestra todos los resultados ajustados (incluidas las referencias) para los superconcentradores. [1]: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.3637
Hung Q. Ngo
Gracias por la aclaración. Nunca he entendido las diferencias entre ellos.
Suresh Venkat

Respuestas:

12

La referencia predeterminada es la encuesta de Ronen Shaltiel . Esto es anterior a los importantes resultados de [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] etc. Creo que el Ph.D de Anup Rao . La tesis es una buena referencia reciente que describe estos desarrollos.

arnab
fuente