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

Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

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 >>>