Pseudorandomness in simple models of computation
(A. Bogdanov)

A pseudorandom generator is an efficiently computable low entropy source of randomness that looks uniformly random to a given class of algorithms. Pseudorandom generators have numerous applications in cryptography and in deterministic simulations of randomized processes. While it is believed that general purpose pseudorandom generators can be constructed, proving their existence is a major open problem in the theory of computation.

We investigate constructions of pseudorandom generators for certain simple classes of algorithms, such as small depth circuits, low degree polynomials, and space bounded computations.