Pseudorandom Generators: A Primer by Oded Goldreich Appeared 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.

Material available on-line

• Author copy: in PDF, June 2010.
• Drafts: in PS and PDF formats, July 2008.
  (Warning: the figures do not appear in this PDF version.)

Related Material available on-line

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