Technical Report CS747
||TOWARDS A COMPUTATIONAL THEORY OF STATISTICAL TESTS.
|| M. Blum and O. Goldreich
|PDF - Revised||CS0747.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).
|Copyright||The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1992/CS/CS0747), 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