Technical Report CS747

Authors: M. Blum and O. Goldreich
PDF - RevisedCS0747.revised.pdf

We initiate a computational theory of statistical tests. Loosely speaking, we say that an algorithm is a statistical test if it rejects ``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).

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1992
To the main CS technical reports page

Computer science department, Technion