Surveys and Papers on Pseudorandomness

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.

Surveys (available on-line)

Chapters in Books

Lecture notes (available on-line)

See also notes for a one-hour overview talk, 2006.

Papers (available on-line)

The following list includes not only papers that deal with the archetypical notion of pseudorandomness but also papers that deal with other notions of pseudorandomness. Unfortunately, older papers (e.g., typically those from the 1980's) are not available online.

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