##
Pseudorandom Generators and the Frequency of Simplicity, or...
Just What Does the NSA Do with Shoo-Fly Pie and Whipped Cream?

Lane A. Hemaspaandra

Computer Science Department

University of Rochester

lane@cs.rochester.edu
### ABSTRACT

In the 1980s, Allender showed that if there are dense polynomial-time
decidable languages containing only a **finite** set of non-random
strings, then all pseudorandom generators are insecure. We extend
this by proving that if there are dense polynomial-time decidable (or
even BPP) languages containing only a **sparse** set of non-random
strings, then all pseudorandom generators are insecure. Terms such as
pseudorandom generator, sparse, etc. will be defined in the talk, and
so no background will be assumed other than a standard knowledge of
the computers and whipped cream.

Colloquia Series page.