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.

- Chapter 3 in Modern Cryptography,
Probabilistic Proofs and Pseudorandomness (1998)
is an earlier version of the foregoing primer.

A revised version appears as Chapter 8 in a book on Complexity theory (2008). - Chapter 3 in Foundations of Cryptography (2001) focuses on the archetypical case of pseudorandom generators (withstanding any polynomial-time distinguisher).

- O. Goldreich, Lecture Notes on Pseudorandomness - Part I (polynomial-time generators), 2000. [in PDF].
- L. Trevisan, Lecture Notes on Pseudorandomness - Part II (derandomization), 2000. [in PDF].

- O. Goldreich,
Randomness, Interaction, Proofs and Zero-Knowledge, 1987.
[in PDF].

See a revised version of the part on Computational Randomness, 1987 (rev. 1997). [in PDF]. - O. Goldreich, N. Nisan and A. Wigderson, On Yao's XOR-Lemma, March 1995.
- O. Goldreich, Pseudorandomness, 1999. ( extended, 2000.) [in PDF].
- O. Goldreich,
Pseudorandom
Generators, Jan. 2006.
[in PDF].

[This is a self-contained version of an eraly draft of chapter 8 of a book on Complexity theory.] - O. Goldreich,
Pseudorandom
Generators - A Primer, Jul. 2008.
[in PDF].

This is the latest and most recommended exposition. It provides a comprehensive treatment of the basic notions and results, and contains proof outlines and/or sketches for the main results. [This is a self-contained and abbreviated version of chapter 8 of a book on Complexity theory.]

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