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

Related Material available on-line

A webpage on Pseudorandomness, including access to alternative expositions and papers. See also a webpage on Computational Complexity, including access to drafts of a recent book.

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