## Towards a Computational Theory of Statistical Tests

#### Webpage for a paper by Manuel Blum and Oded Goldreich

#### Abstract

We initiate a computational theory of statistical tests.
Loosely speaking,
we say that an algorithm is a *statistical test*
if it rejects a ``negligible'' fraction of strings.
We say that a statistical test is *universal* for a class of
algorithms if it rejects all (but finitely many) of the strings
rejected by each algorithm in the class.

We consider the existence and efficiency of universal statistical tests
for various classes of statistical tests.
We also consider the relation between ensembles passing
statistical tests of particular complexity and ensembles which
are indistinguishable from uniform by algorithms of the same complexity.

Some of our results refer to relatively simple statistical tests
(e.g., those implemented by counter machines).
In addition to their own merit,
we hope that these results will stimulate investigations
directed towards results that refer to more complex statistical tests
(e.g., those implemented in log-space).

#### Material available on-line

- First version posted:
1992.

Back to
either Oded Goldreich's homepage
or general list of papers.