Surveys on Pseudorandomness and Computational Indistingushability

by Oded Goldreich

A fresh view at the question of randomness was taken in the theory of computing: It has been postulated that a distribution is 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.

A Primer

The aforementioned approach is surveyed in a primer on pseudorandom generators, which was published in the ULECT series (Nr. 55) of the AMS, 2010. See freely available drafts. Related texts are listed below.

Chapters in Book

Lecture notes (available on-line)

Surveys (available on-line)

See also papers on pseudorandomness.

Back to
Oded Goldreich's homepage or to the full list of papers.