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.

- O. Goldreich,
Pseudorandom Generators - A Primer,
July 2008.

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.] - O. Goldreich, Pseudorandomness, 1999. (extended, 2000.)
- O. Goldreich, N. Nisan and A. Wigderson, On Yao's XOR-Lemma, March 1995.
- O. Goldreich,
Randomness,
Interaction, Proofs and Zero-Knowledge, 1987.

See a revised version of the part on Computational Randomness, 1987 (rev. 1997).

- Chapter 8 in Computational Complexity: A Conceptual Perspective (2008) provides a revised and extended version of the above.
- Chapter 3 in Foundations of Cryptography (Vol. 1, 2001) focuses on the archetypical case of pseudorandom generators (withstanding any polynomial-time distinguisher).
- Chapter 3 in Modern Cryptography, Probabilistic Proofs and Pseudorandomness (1998) surveys the above mentioned approach.

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

- N. Alon, O. Goldreich J. Hastad and R. Peralta,
Simple
Constructions of Almost
*k*-wise Independent Random Variables, June 1992. (See also an Addendum.) - Z. Bar-Yossef, O. Goldreich, and A. Wigderson, Deterministic Amplification of Space Bounded Probabilistic Algorithms, 1998.
- M. Bellare, O. Goldreich and S. Goldwasser, Randomness in Interactive Proofs, August 1991. Addendum, May 1997.
- Z. Brakerski and O. Goldreich, From absolute distinguishability to positive distinguishability, March 2009.
- R. Canetti, G. Even and O. Goldreich, Lower Bounds for Sampling Algorithms for Estimating the Average, October 1994.
- G. Even, O. Goldreich, M. Luby, N. Nisan and B. Velickovic,

Approximations of General Independent Distributions, 1992. - O. Goldreich, A Note on Computational Indistinguishability, 1989.
- O. Goldreich, S. Goldwasser and S. Micali, How to Construct Random Functions, 1984.
- O. Goldreich, S. Goldwasser and A. Nussboim, On the Implementation of Huge Random Objects, 2003.
- O. Goldreich, R. Impagliazzo, L.A. Levin, R. Venkatesan and D. Zuckerman, Security Preserving Amplification of Hardness, August 1990.
- O. Goldreich and L.A. Levin, Hard-core Predicates for any One-way Function, 1989.
- O. Goldreich and B. Meyer, Computational Indistinguishability -- Algorithms vs. Circuits, December 1996.
- O. Goldreich and S. Micali, Increasing the Expansion of Pseudorandom Generators, 1984.
- O. Goldreich, N. Nisan and A. Wigderson, On Yao's XOR-Lemma, March 1995.
- O. Goldreich and M. Sudan, Computational Indistinguishability: A Sample Hierarchy, March 1998.
- O. Goldreich, S. Vadhan, and A. Wigderson, Simplified derandomization of BPP using a hitting set generator, Dec. 1999.
- O. Goldreich and A. Wigderson, Improved derandomization of BPP using a hitting set generator, May 1999.
- O. Goldreich and A. Wigderson, On Pseudorandomness with respect to Deterministic Observers, May 2000.
- O. Goldreich and A. Wigderson, Deradomization that is rarely wrong from short advice that is typically good, 2002.
- O. Goldreich and A. Wigderson, Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing, November 1994.
- O. Goldreich and D. Zuckerman, Another proof that BPP subseteq PH (and more), September 1997.

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