Next: On the Complexity of
Up: The Technion Period (1986-94)
Previous: Approximations of General Independent
This work initiates a computational theory of statistical tests,
which are algorithms that reject only a negligible fraction
of the possible strings.
The work studies the existence and efficiency of universal statistical
tests for various classes of statistical tests, where a
test is called universal for a class if it rejects all
(but finitely many) of the strings
rejected by any statistical test in the class.
Comments:
Authored by M. Blum and O. Goldreich. Appeared in
- Proc. of the 33rd FOCS, pp. 406-416, 1992.
Oded Goldreich
2003-07-30