Pseudorandom Generator - Pseudorandom Generators and Derandomization

Pseudorandom Generators and Derandomization

Pseudorandom generators can be used for efficient deterministic simulations of randomized algorithms. In such applications, the class F describes the computations that one wants to simulate, and one is interested in designing an "efficiently computable" pseudorandom generator against F whose seed length is as short as possible. The deterministic simulation proceeds by replacing the random input to the randomized algorithm by the output of the pseudorandom generator and averaging the outputs produced by the algorithm as the pseudorandom generator is computed over all possible seeds.