Some Complexity Related Papers by Oded Goldreich
last updated: Feb. 2007
NOTE: This page is casually updated.
In case you don't find some paper here,
please look at the general list of papers.
See brief surveys (2000 and 2004),
a book (2008),
and other material.
The following papers can be obtained in PostScript
(papers in REVERSE CHRONOLOGICAL ORDER):
- A. Akavia, O. Goldreich, S. Goldwasser, and D. Moshkovitz,
On Basing One-Way Functions on NP-Hardness,
2005.
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan,
Short PCPs verifiable in polylogarithmic
time, 2005
- O. Goldreich, Bravely, Moderately:
A Common Theme in Four Recent Results, August 2005.
- O. Goldreich, On Promise Problems
(a survey in memory of Shimon Even), January 2005.
- O. Goldreich,
Short Locally Testable Codes and Proofs (survey),
July 2004.
- O. Goldreich, M. Sudan and L. Trevisan,
From logarithmic advice to single-bit advice, 2004.
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan,
Robust PCPs of Proximity, Shorter PCPs
and Applications to Coding, March 2004.
- O. Goldreich, S. Goldwasser and A. Nussboim,
On the Implementation of Huge Random Objects, 2003.
- E. Ben-Sasson, O. Goldreich and M. Sudan,
Bounds on 2-Query Codeword Testing, 2003.
- O. Goldreich and M. Sudan, Locally Testable
Codes and PCPs of Almost-Linear Length, August 2002.
- O. Goldreich and A. Wigderson, Deradomization
that is rarely wrong from short advice that is typically good, 2002.
- O. Goldreich,
Using
the FGLSS-reduction to Prove Inapproximability Results
for Minimum Vertex Cover in Hypergraphs, 2001.
- B. Barak and O. Goldreich,
Universal Arguments and their Applications, 2001.
- O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan,
Lower Bounds for Linear Locally Decodable Codes
and Private Information Retrieval, 2001.
- B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan
and K. Yang,
On the (Im)possibility of Obfuscating
Programs, 2001.
- O. Goldreich, S. Vadhan, and A. Wigderson, On
Interactive Proofs with a Laconic Prover, 2001.
- O. Goldreich and L. Trevisan, Three
Theorems regarding Testing Graph Properties, 2001.
- O. Goldreich, Candidate
One-Way Functions Based on Expander Graphs, 2000.
- O. Goldreich and A. Wigderson,
On
Pseudorandomness with respect to Deterministic Observers, May 2000.
- 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, D. Micciancio, S. Safra, and J.P. Seifert,
Approximating shortest lattice vectors is not harder than
approximating closest lattice vectors, 1999.
- O. Goldreich, A. Sahai and S. Vadhan,
Can
Statistical Zero-Knowledge be Made Non-Interactive?
or On the Relationship of SZK and NISZK, 1998.
- O. Goldreich and S. Vadhan,
Comparing
Entropies in Statistical Zero-Knowledge with Applications
to the Structure of this Class, 1998.
- Z. Bar-Yossef, O. Goldreich, and A. Wigderson,
Deterministic
Amplification of Space Bounded Probabilistic Algorithms, 1998.
- M. Bellare, O. Goldreich and E. Petrank,
Uniform Generation of NP-witnesses using an NP-oracle, 1998.
- O. Goldreich and M. Sudan,
Computational Indistinguishability: A Sample Hierarchy, March 1998.
- O. Goldreich, A. Sahai and S. Vadhan,
Honest-Verifier
Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge, 1998.
- O. Goldreich and D. Zuckerman,
Another proof that BPP subseteq PH (and more), September 1997.
- O. Goldreich and S. Goldwasser, On the
Limits of Non-Approximability of Lattice Problems, Sept. 1997.
- O. Goldreich,
A
Computational Perspective on Sampling (survey), May 1997.
- O. Goldreich and B. Meyer,
Computational Indistinguishability - Algorithms vs. Circuits,
December 1996.
- O. Goldreich, and S. Safra,
A Combinatorial Consistency Lemma
with application to the PCP Theorem, 1996.
- O. Goldreich and A. Wigderson,
On
the Circuit Complexity of Perfect Hashing, July 1996.
- O. Goldreich and E. Petrank,
Quantifying Knowledge Complexity, revised July 1996.
- O. Goldreich and J. Hastad,
On the Complexity of Interactive Proof with Bounded Communication,
Feb. 1996. (rev. April 1997)
- M. Bellare, O. Goldreich and M. Sudan,
Free Bits, PCPs and Non-Approximability, 1995.
- I. Damgard, O. Goldreich and A. Wigderson,
Information Theory versus Complexity Theory: Another Test Case,
September 1995.
- O. Goldreich, L.A. Levin and N. Nisan ,
On Constructing 1-1 One-Way Functions, June 1995.
- O. Goldreich,
Probabilistic Proof Systems (survey), 1995.
- O. Goldreich, N. Nisan and A. Wigderson,
On Yao's XOR-Lemma, March 1995.
- O. Goldreich, R. Ostrovsky and E. Petrank,
Computational Complexity and Knowledge Complexity, revised March 1995.
- O. Goldreich and A. Wigderson,
Tiny Families of Functions with Random Properties:
A Quality-Size Trade-off for Hashing, November 1994.
- R. Canetti, G. Even and O. Goldreich,
Lower Bounds for Sampling Algorithms for Estimating the Average,
October 1994.
- M. Blum and O. Goldreich,
Towards a Computational Theory of Statistical Tests, 1992.
- G. Even, O. Goldreich, M. Luby, N. Nisan and B. Velickovic,
Approximations of General Independent
Distributions, 1992.
- R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad,
D. Ranjan and P. Rohatgi,
The Random Oracle Hypothesis is False, July 1992.
- N. Alon, O. Goldreich J. Hastad and R. Peralta,
Simple Constructions of Almost $k$-wise Independent Random Variables,
June 1992. (See also
an Addendum.)
- M. Bellare, O. Goldreich and S. Goldwasser,
Randomness in Interactive Proofs, August 1991.
Addendum,
May 1997.
- O. Goldreich,
Three XOR-Lemmas - An Exposition, July 1991.
- O. Goldreich, R. Impagliazzo, L.A. Levin,
R. Venkatesan and D. Zuckerman,
Security Preserving Amplification of Hardness, August 1990.
- R. Canetti and O. Goldreich,
Bounds on Tradeoffs between Randomness and Communication Complexity,
August 1990.
- O. Goldreich and L.A. Levin,
Hard-core Predicates for any One-way Function, 1989.
See
Three XOR-Lemmas - An Exposition.
- O. Goldreich,
A Note on Computational Indistinguishability, 1989.
- S. Ben-David, B. Chor, O. Goldreich and M. Luby,
On the Theory of Average Case Complexity, 1989.
- M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos,
On
Completeness and Soundness in Interactive Proof Systems, 1989.
- O. Goldreich,
Randomness, Interaction, Proofs and Zero-Knowledge (a survey), 1987.
(Appeared in The Universal Turing Machine: A Half-Century Survey,
R. Herken (ed.), Oxford University Press, 1988.)
- O. Goldreich and S. Micali,
Increasing the Expansion of Pseudorandom Generators, 1984.
Low quality PostScript files of very old papers
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers