Surveys by Oded Goldreich
last updated: Feb 2024
The following surveys (listed in chronological order)
can be obtained in either PostScript or PDF.
Typically, files dated before 2011 are in PostScript,
but PDF versions of all PostScript files are available
at the directory PSX.
- O. Goldreich,
Randomness, Interaction, Proofs and Zero-Knowledge, 1987.
- O. Goldreich, Towards a Theory of Average Case Complexity, 1988.
- O. Goldreich,
Three XOR-Lemmas - An Exposition, July 1991.
- O. Goldreich, N. Nisan and A. Wigderson,
On Yao's XOR-Lemma, March 1995.
- O. Goldreich,
Probabilistic Proof Systems (surveys and notes),
1995-2008.
- O. Goldreich,
A
Computational Perspective on Sampling (survey), May 1997.
- O. Goldreich,
The Foundations of Cryptography -- An Essay,
June 1997.
- O. Goldreich,
Combinatorial Property Testing -- A Survey, 1997.
- O. Goldreich,
Review of the AS+ALMSS papers (NP=PCP[log,O(1)]), 1999.
- O. Goldreich,
Pseudorandomness, 1999.
(extended,
2000.)
- O. Goldreich,
Preface
to JofC's special issue on General Secure Multi-Party Computation, 1999.
- O. Goldreich,
Computational Complexity - a brief survey, 2000.
- O. Goldreich, M. Sudan, L. Trevisan and S. Vadhan,
Lecture Notes on Probabilistic Proofs
and Pseudorandomness, 2000.
- O. Goldreich,
A Taste of Randomized Computations,
1998, adapted 2001.
- O. Goldreich,
Cryptography and Cryptographic Protocols,
2001.
- O. Goldreich,
Zero-Knowledge twenty years after their invention,
2002.
- O. Goldreich,
Preface
to JofC's special issue on Encryption in the Bounded Storage Model, 2003.
- O. Goldreich,
Foundations of Cryptography (a primer),
July 2004.
- O. Goldreich,
Short Locally Testable Codes and Proofs (survey),
July 2004.
- O. Goldreich and A. Wigderson,
Computational Complexity, 2004.
- O. Goldreich, On Promise Problems
(a survey in memory of Shimon Even), January 2005.
- O. Goldreich, Bravely, Moderately:
A Common Theme in Four Recent Results, August 2005.
- O. Goldreich, Randomness and Computation, Dec. 2005.
- O. Goldreich and M. Sudan,
Preface
to SICOMP's special issue on Randomness and Complexity, March 2006.
- O. Goldreich and S. Vadhan,
Preface
to CC's special issue on Worst-Case vs Average-Case complexity, June 2007.
- O. Goldreich,
Probabilistic Proof Systems - A Primer,
Jun. 2008.
- O. Goldreich,
Pseudorandom Generators - A Primer, July 2008.
- O. Goldreich,
A Brief Introduction to Property Testing,
March 2010.
- O. Goldreich,
Introduction to Testing Graph Properties, March 2010.
- O. Goldreich,
General Cryptographic Protocols: The Very Basics,
March 2010.
- O. Goldreich and S. Vadhan,
On the complexity of computational problems regarding
distributions, 2010.
- O. Goldreich,
Invitation
to Complexity Theory, 2011.
- O. Goldreich,
On the
Use of Complexity in Cryptography, 2011.
- O. Goldreich, On doubly-efficient
interactive proof systems, July 2017. Includes/superseeds
- O. Goldreich, Open Problems in Property Testing of Graphs, June 2021.
- O. Goldreich,
On the Locally Testable Codes of Dinur et al
(with Constant Rate, Distance, and Locality), 2021.
- O. Goldreich, A conceptual introduction to Mathematics
(following the book of A.H. Fraenkel [1942]), Dec 2023.
- O. Goldreich, On locally-characterized expander graphs (a survey), Jan 2024.
- O. Goldreich,
On the relaxed LDC of BGHSV: A survey that corrects the record, Apr 2024.
- O. Goldreich, On the Cook-Mertz
Tree Evaluation procedure, June 2024.
See also books and lecture notes
by Oded Goldreich.
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers