Pseudorandom Generator - Constructions of Pseudorandom Generators

Constructions of Pseudorandom Generators

Efficient constructions of pseudorandom generators are known for several natural classes of functions, including the following ones.

• The class of functions computable by randomized logspace Turing Machines that produce a single bit of output.
• The class of functions computable by randomized constant depth circuits that produce a single bit of output.
• The class of linear functions in many variables over some finite field F_q. These pseudorandom generators are sometimes called epsilon-biased generators.
• The class of polynomials of low degree in many variables over some finite field F_q. (See pseudorandom generators for polynomials.)