## Pseudorandom Generators: A Primer## by Oded GoldreichAppeared in the ULECT series (Nr. 55) of the AMS, 2010.[114 pp., Softcover, ISBN-10: 0-8218-5192-6, ISBN-13: 978-0-8218-5192-0] |

A fresh view at the question of randomness has been taken by complexity theory: It has been postulated that a distribution is random (or rather pseudorandom) if it cannot be told apart from the uniform distribution by any efficient procedure. This paradigm, originally associating efficient procedures with polynomial-time algorithms, has been applied also with respect to a variety of limited classes of such distinguishing procedures.

Starting with the general paradigm, this primer survey the archetypical case of general-purpose pseudorandom generators (withstanding any polynomial-time distinguisher), as well as the derandomization of complexity classes such as BPP, generators withstanding space-bounded distinguishers, and some special-purpose generators.

**Author copy: in PDF, June 2010.**- Drafts: in
PS
and
PDF
formats, July 2008.

(Warning: the figures do not appear in this PDF version.)

Back to the Pseudorandomness page or to Oded Goldreich's homepage.