DETERMINISTIC SIMULATION OF PROBABILISTIC CONSTANT DEPTH CIRCUITS.

Abstract

The authors explicitly construct, for every integer n and epsilon less than 0, a family of functions (pseudorandom bit generators) with the following property: for a random seed, the pseudorandom output 'looks random' to any polynomial-size, constant-depth, unbounded fan-in circuit. Moreover, the functions themselves can be computed by uniform, polynomial-size, constant-depth circuits.