A few years ago, I took a class on complexity theory from Steven Rudich, and I remember him giving an interesting lecture connecting statistical tests (as found in statistics departments!) with circuit complexity. I remember him claiming something vaguely like: you could use circuits to abstractly characterize what a statistical test was, and that there were fundamental limits on what sorts of patterns statistical tests could identify.

Unfortunately, I remember neither precisely what his claim was, nor even enough keywords to let me Google for it. Does anyone know what he could have meant, and supply me with some references?

(My apologies for the vagueness of this question: if I knew enough to ask precisely, I wouldn't need to ask!)


1 Answer 1


I think I remember what lecture you're talking about. I remember he was saying that most statistical tests that are done can be carried out in $LOGSPACE$. (Comparing the number of $1$'s versus the number of $0$'s, computing standard deviation, etc.) But the output of Nisan's pseudorandom generator will fool all of these statistical tests, and still is not a truly random sequence. This lecture by Ryan O'Donnell describes the details.

An alternative way of defining "statistical test" is given by Blum and Goldreich.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.