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.
Back to the Pseudorandomness page or to Oded Goldreich's homepage.