Towards a Computational Theory of Statistical Tests (Extended 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).