Surveys by Oded Goldreich
last updated: June 2017
The following surveys (listed in chronological order)
can be obtained in PostScript:
- 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.
See also books and lecture notes
by Oded Goldreich.
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers