Some Papers by Oded Goldreich
last updated: Sept 2024
Few of my old paper (predating 1990) and almost all
of my papers postdating 1990 can be found here.
Also available are partial lists of
See also my list of publication and
slides of talks.
The following papers can be obtained in PostScript or PDF
(papers are ordered by the full author-list):
PDF versions of all PostScript files are available
at the directory PSX.
- A. Akavia, O. Goldreich, S. Goldwasser, and D. Moshkovitz,
On Basing One-Way Functions on NP-Hardness,
2005.
- W. Alexi, B. Chor, O. Goldreich, and C.P. Schnorr,
On the hardness of the least-signficant bits
of the RSA and Rabin functions, 1984.
- N. Alon, O. Goldreich J. Hastad and R. Peralta,
Simple Constructions of Almost $k$-wise
Independent Random Variables, June 1992.
- N. Alon, O. Goldreich Y. Mansour, Almost $k$-wise
independence versus $k$-wise independence, 2002
- N. Amir, O. Goldreich, and G. Rothblum.
Doubly Sub-linear Interactive Proofs of Proximity,
Sept 2024.
- L. Avigad and O. Goldreich,
Testing Graph Blow-Up, March 2010.
- B. Awerbuch, O. Goldreich, D. Peleg, and R. Vainish,
A Trade-off between Information and Communication in Broadcast Protocols,
June 1989.
[in PDF].
- M. Ball, O. Goldreich, and T. Malkin, Randomness
Extraction from Somewhat Dependent Sources, Dec 2019.
- M. Ball, O. Goldreich, and T. Malkin, Communication
Complexity with Defective Randomness, April 2020.
- B. Barak and O. Goldreich,
Universal Arguments and their Applications, 2001.
- B. Barak, O. Goldreich, S. Goldwasser and Y. Lindell,
Resettably-Sound
Zero-Knowledge and its Applications, 2001.
[in PDF].
- B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan
and K. Yang,
On the (Im)possibility of Obfuscating
Programs, 2001.
- K. Barhum, O. Goldreich, and A. Shraibman,
On approximating the average distance
between points, 2007.
- R. Bar-Yehuda, O. Goldreich, and A. Itai,
On the Time-Complexity of Broadcast in Radio Networks:
An Exponential Gap Between Determinism and Randomization
(abstract and errarata), 1992.
- Z. Bar-Yossef, O. Goldreich, and A. Wigderson,
Deterministic
Amplification of Space Bounded Probabilistic Algorithms, 1998.
[in PDF].
- M. Bellare and O. Goldreich,
On Defining Proofs of Knowledge, 1992.
See also our notes on
Proofs of Computational Ability (1992).
[in PDF].
- M. Bellare and O. Goldreich,
On Probabilistic versus Deterministic Provers
in the Definition of Proofs Of Knowledge, 2006.
- M. Bellare, O. Goldreich and S. Goldwasser,
Randomness in Interactive Proofs, August 1991.
[in PDF].
Addendum,
May 1997.
[in PDF].
- M. Bellare, O. Goldreich and S. Goldwasser,
Incremental Cryptography, 1995.
- M. Bellare, O. Goldreich and H. Krawczyk,
Stateless
evaluation of pseudorandom functions: Security
beyond the birthday barrier, 1999.
(Available
in multiple formats from Mihir's page.)
[in PDF].
- M. Bellare, O. Goldreich and A. Mityagin,
The Power of Verification Queries
in Message Authentication and Authenticated Encryption, 2004.
- M. Bellare, O. Goldreich and E. Petrank,
Uniform Generation of NP-witnesses using an NP-oracle, 1998.
[in PDF].
- M. Bellare, O. Goldreich and M. Sudan,
Free Bits, PCPs and Non-Approximability, 1995.
- S. Ben-David, B. Chor, O. Goldreich and M. Luby,
On the Theory of Average Case Complexity, 1989.
[in PDF].
- M. Ben-Or, R. Canetti and O. Goldreich,
Asynchronous Secure Computation, 1993.
See
Ran Canetti's PhD Thesis, 1995. (over 100 pages, 1.4M)
[in PDF].
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan,
Robust PCPs of Proximity, Shorter PCPs
and Applications to Coding, March 2004.
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan,
Short PCPs verifiable in polylogarithmic time, 2005
- E. Ben-Sasson, O. Goldreich and M. Sudan,
Bounds on 2-Query Codeword Testing, 2003.
- I. Benjamini and O. Goldreich,
Pseudo-Mixing Time of Random Walks June 2019.
- M. Blum and O. Goldreich,
Towards a Computational Theory of Statistical Tests,
1992.
[in PDF].
- Z. Brakerski and O. Goldreich, From absolute
distinguishability to positive distinguishability, March 2009.
- N. Bshouty and O. Goldreich,
On properties that are non-trivial to test, Feb 2022.
- R. Canetti, G. Even and O. Goldreich,
Lower Bounds for Sampling Algorithms for Estimating the Average,
October 1994.
[in PDF].
- R. Canetti, U. Feige, O. Goldreich and M. Naor,
Adaptively Secure Multi-party Computation,
TR-682, LCS/MIT, 1996.
[in PDF].
- R. Canetti and O. Goldreich,
Bounds
on Tradeoffs between Randomness and Communication Complexity,
August 1990.
[in PDF].
- R. Canetti, O. Goldreich, S. Goldwasser and S. Micali,
Resettable Zero-Knowledge, 1999.
[in PDF].
- R. Canetti, O. Goldreich, S. Halevi,
The Random Oracle Methodology, Revisited,
March 1998.
[in PDF].
- R. Canetti, O. Goldreich, S. Halevi,
On the random-oracle methodology as applied to
length-restricted signature schemes, July 2003.
[in PDF].
- R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad,
D. Ranjan and P. Rohatgi,
The Random Oracle Hypothesis is False, July 1992.
[in PDF].
- B. Chor, J. Freidmann, O. Goldreich, J. Hastad,
S. Rudich and R. Smolensky,
The Bit Extraction Problem or t-Resilient Functions, 1985.
[in PDF].
- B. Chor and O. Goldreich,
On the power of two-points based sampling, 1985.
[in PDF].
- B. Chor and O. Goldreich,
Unbiased Bits From Sources of Weak
Randomness and Probabilistic Communication Complexity, 1986.
- B. Chor and O. Goldreich,
An
Improved Parallel Algorithm for Integer GCD, 1990.
- B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan,
Private Information Retrieval, 1995.
[in PDF].
- A. Czumaj, O. Goldreich, D. Ron, C. Seshadhri, A. Shapira, and C. Sohler,
Finding Cycles and Trees in Sublinear Time,
April 2010.
- I. Damgard, O. Goldreich, T. Okamoto and A. Wigderson,
Honest Verifier vs Dishonest Verifier
in Public Coin Zero-Knowledge Proofs (Extended Abstract),
September 1995.
[in PDF].
See also
partial version
by Damgard, Goldreich, and Wigderson, November 1994.
[in PDF].
- I. Damgard, O. Goldreich and A. Wigderson,
Information Theory versus Complexity Theory: Another Test Case,
September 1995.
[in PDF].
- S. Decatur, O. Goldreich, and D. Ron,
Computational
Sample Complexity, April 1997.
[in PDF].
- I. Dinur, O. Goldreich, and T. Gur, Every set
in P is strongly testable under a suitable encoding, Mar 2018.
- Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron,
and A. Samorodnitsky,
Improved
Testing Algorithms for Monotonicity, 1999.
[in PDF].
- G. Even, O. Goldreich, M. Luby, N. Nisan and B. Velickovic,
Approximations of General
Independent Distributions, 1992.
[in PDF].
- S. Even and O. Goldreich,
On the Security
of Multi-Party Ping-Pong Protocols, 1983.
- S. Even, O. Goldreich and S. Micali,
On-Line/Off-Line Digital Signatures, revised 1994.
[in PDF].
- D.M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, and G. Segev,
More Constructions of Lossy
and Correlation-Secure Trapdoor Functions, 2010.
- M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos,
On
Completeness and Soundness in Interactive Proof Systems, 1989.
[in PDF].
- O. Goldreich,
Finding
the Shortest Move-Sequence in the Graph-Generalized
15-Puzzle is NP-Hard, 1984.
- O. Goldreich,
Two Remarks
Concerning the Goldwasser-Micali-Rivest Signature Scheme, 1986.
[in PDF].
- O. Goldreich,
Randomness, Interaction, Proofs and Zero-Knowledge (a survey), 1987.
See a revised version of the part on
Computational Randomness, 1987 (rev. 1997).
[in PDF].
- O. Goldreich, Towards a Theory of Average Case Complexity, 1988.
See revised
Notes
on Levin's Theory of Average-Case Complexity, 1997.
[in PDF].
- O. Goldreich,
A Note on Computational Indistinguishability, 1989.
[in PDF].
- O. Goldreich,
Three XOR-Lemmas - An Exposition, July 1991.
[in PDF].
- O. Goldreich,
A Uniform-Complexity Treatment of Encryption and Zero-Knowledge,
July 1991.
- O. Goldreich,
Probabilistic Proof Systems (survey), 1995.
- O. Goldreich,
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof,
October 1996.
[in PDF].
- 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.
[in PDF].
- O. Goldreich,
Review of the AS+ALMSS papers (NP=PCP[log,O(1)]), 1999.
[in PDF].
- O. Goldreich,
Pseudorandomness (a survey), 1999.
(An extended
version, 2000.)
[in PDF].
- O. Goldreich,
Preface
to Special Issue on General Secure Multi-Party Computation, 1999.
[in PDF].
- O. Goldreich,
On Security Preserving Reductions -
Revised Terminology, Jan. 2000.
- O. Goldreich,
Computational Complexity - a brief survey, 2000.
- O. Goldreich, Candidate
One-Way Functions Based on Expander Graphs, 2000.
- O. Goldreich,
A Taste of Randomized Computations,
1998, adapted 2001.
- O. Goldreich, Cryptography and
Cryptographic Protocols (survey), 2001.
- O. Goldreich, Concurrent Zero-Knowledge
With Timing, Revisited, 2001.
- O. Goldreich,
Using
the FGLSS-reduction to Prove Inapproximability Results
for Minimum Vertex Cover in Hypergraphs, 2001.
[in PDF].
- O. Goldreich,
The GGM Construction does NOT yield
Correlation Intractable Function Ensembles, 2002.
- O. Goldreich,
Zero-Knowledge twenty years after their
invention (survey), 2002.
- O. Goldreich,
Preface
to Special Issue on Encryption in the Bounded Storage Model, 2003.
[in PDF].
- O. Goldreich,
Foundations of Cryptography (a primer),
July 2004.
- O. Goldreich,
Short Locally Testable Codes and Proofs (survey),
July 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, On Expected
Probabilistic Polynomial-Time Adversaries - A suggestion
for restricted definitions and their benefits, August 2006.
- O. Goldreich, On the Average-Case
Complexity of Property Testing, July 2007.
- O. Goldreich, A Candidate Counterexample
to the Easy Cylinders Conjecture, March 2009.
- O. Goldreich,
On Testing Computability by Small Width OBDDs,
April 2010.
- O. Goldreich, In a World of P=BPP,
August 2010.
- O. Goldreich, Two Comments on
Targeted Canonical Derandomizers, April 2011.
- O. Goldreich, On the Effect of the Proximity
Parameter on Property Testers, Feb. 2012.
- O. Goldreich, On Multiple Input Problems
in Property Testing, May 2013.
- O. Goldreich, On the Communication Complexity
Methodology for Proving Lower Bounds on the Query Complexity
of Property Testing, May 2013.
- O. Goldreich, The uniform distribution is complete
with respect to testing identity to a fixed distribution, Feb. 2016.
- O. Goldreich, Reducing testing affine spaces
to testing linearity, May 2016.
- O. Goldreich, Deconstructing 1-local expanders,
Sept 2016.
- O. Goldreich, Hierarchy Theorems
for Testing Properties in Size-Oblivious Query Complexity, May 2018.
- O. Goldreich, Flexible models
for testing graph properties, May 2018.
- O. Goldreich, Testing Graphs
in Vertex-Distribution-Free Models , Oct. 2018.
- O. Goldreich, Multi-pseudodeterministic
algorithms, Jan. 2019.
- O. Goldreich, Testing Bipartitness
in an Augmented VDF Bounded-Degree Graph Model, May 2019.
- O. Goldreich, On the Complexity of
Estimating the Effective Support Size, June 2019.
- O. Goldreich, Testing Isomorphism
in the Bounded-Degree Graph Model, August 2019.
- O. Goldreich, Improved bounds on
the AN-complexity of multilinear functions, Nov. 2019.
- O. Goldreich,
On Counting $t$-Cliques Mod 2, July 2020.
- O. Goldreich, On Testing Hamiltonicity
in the Bounded Degree Graph Model, July 2020.
- O. Goldreich, On Testing Asymmetry
in the Bounded Degree Graph Model, August 2020.
- O. Goldreich, Robust Self-Ordering
versus Local Self-Ordering, March 2021.
- O. Goldreich, On the Lower Bound
on the Length of Relaxed Locally Decodable Codes, May 2023.
- O. Goldreich, On the complexity
of enumerating ordered sets, Sept. 2023.
- O. Goldreich, On coarse
and fine approximate counting of $t$-cliques, Sept. 2023.
- O. Goldreich, On the query complexity of
testing local graph properties in the bounded-degree graph model,
Mar. 2024.
- O. Goldreich, Solving Tree Evaluation
in $o(\log n \cdot \log\log n)$ space, July 2024.
- O. Goldreich and S. Goldwasser, On the
Limits of Non-Approximability of Lattice Problems, Sept. 1997.
- O. Goldreich and S. Goldwasser,
On the
possibility of basing Cryptography on the assumption that P neq NP,
Feb. 1998.
[in PDF].
- O. Goldreich, S. Goldwasser and S. Halevi,
Using Lattice Problems in Cryptography
- O. Goldreich, S. Goldwasser, E. Lehman, D. Ron and A. Samorodnitsky,
Testing Monotinicity, 1998 (improved 1999).
- O. Goldreich, S. Goldwasser and N. Linial,
Fault-tolerant Computation in the Full Information Model,
revised October 1995.
[in PDF].
- O. Goldreich, S. Goldwasser and S. Micali,
How to Construct Random Functions, 1984.
- O. Goldreich, S. Goldwasser and S. Micali,
Interleaved Zero-Knowledge, 1999.
[in PDF].
- O. Goldreich, S. Goldwasser and A. Nussboim,
On the Implementation of Huge Random Objects, 2003.
- O. Goldreich, S. Goldwasser and D. Ron,
Property Testing
and its connection to Learning and Approximation, 1996.
- O. Goldreich, S. Goldwasser, and D. Ron,
On the possibilities and limitations
of pseudodeterministic algorithms, Aug 2012.
- O. Goldreich and T. Gur,
Universal Locally Testable Codes, Mar. 2016.
- O. Goldreich and T. Gur,
Universal Locally Verifiable Codes
and $3$-Round Interactive Proofs of Proximity for CSP, Nov. 2016.
- O. Goldreich, T. Gur, and I. Komargodski,
Strong Locally Testable Codes
with Relaxed Local Decoders, Feb. 2014.
- O. Goldreich, T. Gur, and R. Rothblum,
Proofs of Proximity for Context-Free Languages
and Read-Once Branching Programs, Feb. 2015.
- O. Goldreich and J. Hastad,
On the Complexity of Interactive Proof with Bounded Communication,
Feb. 1996. (rev. April 1997)
[in PDF].
- O. Goldreich, A. Herzberg, and A. Segall,
A
Quantitative Approach to Dynamic Networks, 1992.
[in PDF].
- O. Goldreich, R. Impagliazzo, L.A. Levin,
R. Venkatesan and D. Zuckerman,
Security Preserving Amplification of Hardness, August 1990.
[in PDF].
- O. Goldreich and R. Izsak,
Monotone Circuits:
One-Way Functions versus Pseudorandom Generators, Sept 2011.
- O. Goldreich, B. Juba, and M. Sudan,
A Theory of Goal-Oriented Communication, Sept 2009.
- O. Goldreich and A. Kahan,
How to Construct Constant-Round Zero-Knowledge Proof Systems for NP,
March 1996.
[in PDF].
- O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan,
Bounds for Linear Locally Decodable Codes and
Private Information Retrieval, 2001.
- O. Goldreich and T. Kaufman,
Proximity Oblivious Testing
and the Role of Invariances, April 2010.
- O. Goldreich, H. Krawczyk, and M. Luby,
Pseudorandom generators based on regular one-way functions ,
1988.
- O. Goldreich and H. Krawczyk,
On Sparse Pseudorandom Distributions, 1989.
- O. Goldreich and H. Krawczyk,
On the Composition of Zero-Knowledge Proof Systems, revised 1994.
- O. Goldreich, M. Krivelevich, I. Newman and E. Rozenberg,
Hierarchy Theorems for Property Testing, Nov. 2008.
- O. Goldreich and L.A. Levin,
Hard-core Predicates for any One-way Function, 1989.
- O. Goldreich, L.A. Levin and N. Nisan,
On Constructing 1-1 One-Way Functions, June 1995.
[in PDF].
- O. Goldreich and M. Leshkowitz, On Emulating
Interactive Proofs with Public Coins, Apr. 2016.
- O. Goldreich and Y. Lindell,
Session-Key Generation
using Human Passwords Only, 2000.
- O. Goldreich, Y. Lustig and M. Naor,
On Chosen
Ciphertext Security of Multiple Encryptions, 2002.
- O. Goldreich and O. Meir The Tensor Product
of Two Good Codes Is Not Necessarily Robustly Testable, 2007.
- O. Goldreich and O. Meir,
Input-Oblivious Proof Systems
and a Uniform Complexity Perspective on P/poly, Feb. 2011.
- O. Goldreich and B. Meyer,
Computational Indistinguishability - Algorithms vs. Circuits,
December 1996.
[in PDF].
- O. Goldreich and S. Micali,
Increasing the Expansion of Pseudorandom Generators, 1984.
[in PDF].
- O. Goldreich, S. Micali, and A. Wigderson,
Zero-Knowledge and Secure Function Computation.
- O. Goldreich, D. Micciancio, S. Safra, and J.P. Seifert,
Approximating shortest lattice vectors is not harder than
approximating closest lattice vectors, 1999.
[in PDF].
- O. Goldreich, N. Nisan and A. Wigderson,
On Yao's XOR-Lemma, March 1995.
- O. Goldreich and R. Ostrovsky,
Software Protection and Simulation on Oblivious RAMs,
revised October 1995.
- O. Goldreich and Y. Oren,
Definitions and properties of Zero-Knowledge proof systems,
an old version (1992?).
[in PDF].
- O. Goldreich, R. Ostrovsky and E. Petrank,
Computational Complexity and Knowledge Complexity,
revised March 1995.
[in PDF].
- O. Goldreich and E. Petrank,
Quantifying Knowledge Complexity,
revised July 1996.
[in PDF].
- O. Goldreich and E. Petrank,
The
Best of Both Worlds: Guaranteeing Termination
in Fast Randomized Byzantine Agreement Protocols, October 1990.
[in PDF].
- O. Goldreich, B. Pfitzmann, and R.L. Rivest,
Self-Delegation with Controlled Propagation, September 1997.
[in PDF].
- O. Goldreich and D. Ron,
A Universal Learning Algorithm, June 1996.
- O. Goldreich and D. Ron,
Property Testing in Bounded-Degree Graphs, 1997
[revised 1999].
- O. Goldreich and D. Ron,
A Sublinear Bipartite Tester for Bounded Degree Graphs, 1997.
[in PDF].
- O. Goldreich and D. Ron,
On
Testing Expansion in Bounded-Degree Graphs, March 2000.
[in PDF].
- O. Goldreich and D. Ron,
On Estimating the Average Degree of a Graph,
2004.
- O. Goldreich and D. Ron,
Approximating Average Parameters of Graphs,
2005.
- O. Goldreich and D. Ron,
Algorithmic Aspects of Property Testing in the
Dense Graphs Model, April 2008.
- O. Goldreich and D. Ron,
On Proximity Oblivious Testing, April 2008.
- O. Goldreich and D. Ron,
On Sample-Based Testers, Aug. 2013.
- O. Goldreich and D. Ron,
On Learning and Testing Dynamic Environments,
Mar. 2014.
- O. Goldreich and D. Ron,
The Subgraph Testing Model, Mar. 2018.
- O. Goldreich and D. Ron, One-Sided Error
Testing of Monomials and Affine Subspaces, May 2020.
- O. Goldreich and D. Ron, A Lower Bound
on the Complexity of Testing Grained Distributions, September 2021.
- O. Goldreich and D. Ron, Testing Distributions
of Huge Objects, September 2021.
- O. Goldreich, D. Ron and M. Sudan,
Chinese
Remaindering with Errors, 1998.
[in PDF].
- O. Goldreich and G. Rothblum,
Simple doubly-efficient interactive proof systems
for locally-characterizable sets , Feb. 2017.
- O. Goldreich and G. Rothblum,
Worst-case to Average-case reductions
for subclasses of P, Aug. 2017.
- O. Goldreich and G. Rothblum,
Counting $t$-cliques: Worst-case to average-case
reductions and Direct interactive proof systems, Mar. 2018.
- O. Goldreich and G. Rothblum,
Constant-round interactive proof systems
for AC0[2] and NC1, Apr. 2018.
- O. Goldreich, G. Rothblum, and T. Skverer,
On Interactive Proofs of Proximity
with Proof-Oblivious Queries , Sept 2022.
- O. Goldreich and R. Rothblum,
Enhancements of Trapdoor Permutations, 2011.
- O. Goldreich and V. Rosen,
On
the Security of Modular Exponentiation with Application to the
Construction of Pseudorandom Generators, 2000.
[in PDF].
- O. Goldreich, R. Rubinfeld and M. Sudan,
Learning polynomials with queries: the highly noisy case, 2000
[in PDF].
- O. Goldreich, and S. Safra,
A Combinatorial Consistency Lemma
with application to the PCP Theorem, 1996.
- O. Goldreich, A. Sahai and S. Vadhan,
Honest-Verifier
Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge, 1998.
[in PDF].
- O. Goldreich, A. Sahai and S. Vadhan,
Can
Statistical Zero-Knowledge be Made Non-Interactive?
or On the Relationship of SZK and NISZK, 1998.
[in PDF].
- O. Goldreich and O. Sheffet, On the randomness
complexity of property testing, Feb. 2007.
- O. Goldreich and I. Shinkar, Two-Sided
Error Proximity Oblivious Testing, Mar. 2012.
- O. Goldreich and M. Sudan,
Computational Indistinguishability: A Sample Hierarchy, March 1998.
[in PDF].
- O. Goldreich and M. Sudan, Locally Testable
Codes and PCPs of Almost-Linear Length, August 2002.
- O. Goldreich, M. Sudan and L. Trevisan,
From logarithmic advice to single-bit advice, 2004.
- O. Goldreich and A. Tal, Matrix Rigidity
of Random Toeplitz Matrices, May 2015.
- O. Goldreich and A. Tal, On Constant-Depth
Canonical Boolean Circuits for Computing Multilinear Functions, Dec 2017.
- O. Goldreich and L. Tauber,
Testing in the bounded-degree graph model
with degree bound two, Dec 2022.
- O. Goldreich and L. Tauber,
On Testing Isomorphism to a Fixed Graph
in the Bounded-Degree Graph Model, Sept 2023.
- O. Goldreich and L. Tauber,
On Testing Group Properties, Dec 2023.
- O. Goldreich and L. Teichner,
Super-Perfect Zero-Knowledge Proofs, July 2014.
- O. Goldreich and L. Trevisan, Three
Theorems regarding Testing Graph Properties, 2001.
- O. Goldreich and S. Vadhan,
Comparing
Entropies in Statistical Zero-Knowledge with Applications
to the Structure of this Class, 1998.
[in PDF].
- O. Goldreich, S. Vadhan, and A. Wigderson,
Simplified
derandomization of BPP using a hitting set generator, Dec. 1999.
[in PDF].
- O. Goldreich, S. Vadhan, and A. Wigderson, On
Interactive Proofs with a Laconic Prover, 2001.
- O. Goldreich and R. Vainish,
How to Solve
any Protocol Problem - An Efficiency Improvement, 1987.
[in PDF].
- O. Goldreich, E. Viola, and A. Wigderson,
On Randomness Extraction in AC0,
January 2015.
- O. Goldreich and A. Wigderson,
Tiny Families of Functions with Random Properties:
A Quality-Size Trade-off for Hashing, 1994.
- O. Goldreich and A. Wigderson,
On
the Circuit Complexity of Perfect Hashing, July 1996.
[in PDF].
- O. Goldreich and A. Wigderson,
Improved
derandomization of BPP using a hitting set generator, May 1999.
[in PDF].
- O. Goldreich and A. Wigderson,
On
Pseudorandomness with respect to Deterministic Observers, May 2000.
[in PDF].
- O. Goldreich and A. Wigderson, Deradomization
that is rarely wrong from short advice that is typically good, 2002.
- O. Goldreich and A. Wigderson,
Computational Complexity (survey), 2004.
- O. Goldreich and A. Wigderson, On the Size
of Depth-Three Boolean Circuits for Computing Multilinear Functions,
March 2013.
- O. Goldreich and A. Wigderson, On
Derandomizing Algorithms that Err Extremely Rarely,
Nov. 2013.
- O. Goldreich and A. Wigderson,
Robustly Self-Ordered Graphs:
Constructions and Applications to Property Testing, Sept 2020.
- O. Goldreich and A. Wigderson,
Non-adaptive vs Adaptive Queries
in the Dense Graph Testing Model, Nov 2020.
- O. Goldreich and A. Wigderson, Constructing
Large Families of Pairwise Far Permutations: Good Permutation Codes
Based on the Shuffle-Exchange Network, Dec 2020.
- O. Goldreich and D. Zuckerman,
Another proof that BPP subseteq PH (and more), September 1997.
See
revision
(2016).
Back to Oded Goldreich's homepage
or to the top of this page.