Circuito complejo y pruebas estadísticas

Hace unos años, tomé una clase sobre teoría de la complejidad de Steven Rudich, y recuerdo que él dio una conferencia interesante que conecta las pruebas estadísticas (¡como se encuentra en los departamentos de estadística!) Con la complejidad del circuito. Lo recuerdo afirmando algo vagamente parecido: se podían usar circuitos para caracterizar de manera abstracta lo que era una prueba estadística, y que había límites fundamentales sobre qué tipo de patrones podían identificar las pruebas estadísticas.

Desafortunadamente, no recuerdo exactamente cuál era su reclamo, ni siquiera suficientes palabras clave para permitirme buscarlo en Google. ¿Alguien sabe lo que podría haber querido decir y me proporciona algunas referencias?

(Mis disculpas por la vaguedad de esta pregunta: si supiera lo suficiente como para preguntar con precisión, ¡no necesitaría preguntar!)

Creo que recuerdo de qué conferencia estás hablando. Recuerdo que estaba diciendo que la mayoría de las pruebas estadísticas que se realizan pueden llevarse a cabo en . (Comparando el número de contra el número de , calculando la desviación estándar, etc.) Pero la salida del generador pseudoaleatorio de Nisan engañará a todas estas pruebas estadísticas, y todavía no es una secuencia verdaderamente aleatoria. Esta conferencia de Ryan O'Donnell describe los detalles.$LOGSPACE$$1$$0$

Blum y Goldreich ofrecen una forma alternativa de definir la "prueba estadística" .