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)
- 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).
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.
- 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.
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.