Pseudorandom Generators

Oded Goldreich (Weizmann Institute)

Talking in the presence of Leonid Levin is the most intellectually frightening experience there is. Failure to survive is guaranteed, and one better choose a glorious way to fail. Of the glorious possibilities closely related to Levin and feasible for me -- i.e., NP-completeness, probabilistic proof systems, and pseudorandomness -- I chose the latter.

I view the concept of pseudorandom generators as a general paradigm having numerous incarnations that share three basic aspects:

1. a stretching (of a random seed to a pseudorandom sequence),


2. a notion of computational indistinguishability (underlying the definition of pseudorandomness),and


3. bounds on the complexity of the stretching (aka generation) process.

I will shortly preview several incarnations starting from the archetypical case, which is tailored to any efficient application, and ending with a few highly restricted notions, which nevertheless have numerous applications.