Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > KENNETH W. REGAN:
All reports by Author Kenneth W. Regan:

TR95-006 | 1st January 1995
Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

Pseudorandom Generators, Measure Theory, and Natural Proofs


This paper proves that if strong pseudorandom number generators or
one-way functions exist, then the class of languages that have
polynomial-sized circuits is not small within exponential
time, in terms of the resource-bounded measure theory of Lutz.
More precisely, if for some \epsilon > 0 there exist nonuniformly
2^{n^{\epsilon}}-hard ... more >>>




ISSN 1433-8092 | Imprint