<p>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. <a href="http://www.cs.cmu.edu/~odonnell/complexity/docs/lecture16.pdf" rel="nofollow">This lecture by Ryan O'Donnell</a> describes the details.</p>

<p>An alternative way of defining "statistical test" is given by <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.917" rel="nofollow">Blum and Goldreich</a>. </p>

CC BY-SA 2.5
2010-09-20T16:29:51.427Z
2010-09-20T16:29:51.427Z
Ryan Williams
<p>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. </p>

<p>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?</p>

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

CC BY-SA 2.5
2010-09-20T16:20:12.203Z
you might also want to check out Laurent Bienvenu's answer to this question: http://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable/1415#1415 for discussion at the realm of computability.
Suresh Venkat
<circuit-complexity><st.statistics>
Circuit complexity and statistical tests
Neel Krishnaswami
# Circuit complexity and statistical tests

(Asked by: username_0 on 2010-09-20)

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!)

**Tags:** circuit-complexity, st.statistics
> **Comments:**
> **username_1**: you might also want to check out Laurent Bienvenu's answer to this question: http://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable/1415#1415 for discussion at the realm of computability.  

---

## 1 answers

### Answer by username_2 on 2010-09-20. Score: 7 | Accepted answer

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](http://www.cs.cmu.edu/~odonnell/complexity/docs/lecture16.pdf) describes the details.

An alternative way of defining "statistical test" is given by [Blum and Goldreich](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.917).


---

