Oded Goldreich
According to our database^{1},
Oded Goldreich
authored at least 360 papers
between 1981 and 2020.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at zbmath.org

at wikidata.org

at scopus.com

at viaf.org

at orcid.org

at id.loc.gov

at dnb.info

at isni.org

at dl.acm.org
On csauthors.net:
Bibliography
2020
A Probabilistic ErrorCorrecting Scheme that Provides Partial Secrecy.
Proceedings of the Computational Complexity and Property Testing, 2020
Pseudomixing Time of Random Walks.
Proceedings of the Computational Complexity and Property Testing, 2020
On the Size of DepthThree Boolean Circuits for Computing Multilinear Functions.
Proceedings of the Computational Complexity and Property Testing, 2020
On ConstantDepth Canonical Boolean Circuits for Computing Multilinear Functions.
Proceedings of the Computational Complexity and Property Testing, 2020
SuperPerfect ZeroKnowledge Proofs.
Proceedings of the Computational Complexity and Property Testing, 2020
ConstantRound Interactive Proof Systems for AC0[2] and NC1.
Proceedings of the Computational Complexity and Property Testing, 2020
WorstCase to AverageCase Reductions for Subclasses of P.
Proceedings of the Computational Complexity and Property Testing, 2020
On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition).
Proceedings of the Computational Complexity and Property Testing, 2020
Bridging a Small Gap in the Gap Amplification of Assignment Testers.
Proceedings of the Computational Complexity and Property Testing, 2020
On Emulating Interactive Proofs with Public Coins.
Proceedings of the Computational Complexity and Property Testing, 2020
On Constructing Expanders for Any Number of Vertices.
Proceedings of the Computational Complexity and Property Testing, 2020
Flexible Models for Testing Graph Properties.
Proceedings of the Computational Complexity and Property Testing, 2020
On the Optimal Analysis of the Collision Probability Tester (an Exposition).
Proceedings of the Computational Complexity and Property Testing, 2020
Deconstructing 1Local Expanders.
Proceedings of the Computational Complexity and Property Testing, 2020
Reducing Testing Affine Spaces to Testing Linearity of Functions.
Proceedings of the Computational Complexity and Property Testing, 2020
The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution.
Proceedings of the Computational Complexity and Property Testing, 2020
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing.
Proceedings of the Computational Complexity and Property Testing, 2020
On the Effect of the Proximity Parameter on Property Testers.
Proceedings of the Computational Complexity and Property Testing, 2020
Two Comments on Targeted Canonical Derandomizers.
Proceedings of the Computational Complexity and Property Testing, 2020
On (Valiant's) PolynomialSize Monotone Formula for Majority.
Proceedings of the Computational Complexity and Property Testing, 2020
OneSided Error Testing of Monomials and Affine Subspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2020
Communication Complexity with Defective Randomness.
Electronic Colloquium on Computational Complexity (ECCC), 2020
2019
Improved bounds on the ANcomplexity of multilinear functions.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Testing Isomorphism in the BoundedDegree Graph Model.
Electronic Colloquium on Computational Complexity (ECCC), 2019
On the Complexity of Estimating the Effective Support Size.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Multipseudodeterministic algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2019
PseudoMixing Time of Random Walks.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Randomness Extraction from Somewhat Dependent Sources.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Testing Bipartitness in an Augmented VDF BoundedDegree Graph Model.
CoRR, 2019
Hierarchy Theorems for Testing Properties in SizeOblivious Query Complexity.
Comput. Complex., 2019
How to play any mental game, or a completeness theorem for protocols with honest majority.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
How to construct random functions.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
On some noncryptographic works of Goldwasser and Micali.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
On the impact of cryptography on complexity theory.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
On the foundations of cryptography.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
Preface.
Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019
2018
On DoublyEfficient Interactive Proof Systems.
Foundations and Trends in Theoretical Computer Science, 2018
Constantround interactive proof systems for AC0[2] and NC1.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Counting tcliques: Worstcase to averagecase reductions and Direct interactive proof systems.
Electronic Colloquium on Computational Complexity (ECCC), 2018
The Subgraph Testing Model.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Testing Graphs in VertexDistributionFree Models.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Flexible models for testing graph properties.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Every set in P is strongly testable under a suitable encoding.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Universal Locally Testable Codes.
Chicago J. Theor. Comput. Sci., 2018
Matrix rigidity of random Toeplitz matrices.
Comput. Complex., 2018
Counting tCliques: WorstCase to AverageCase Reductions and Direct Interactive Proof Systems.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
2017
On Learning and Testing Dynamic Environments.
J. ACM, 2017
On ConstantDepth Canonical Boolean Circuits for Computing Multilinear Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017
Worstcase to Averagecase reductions for subclasses of P.
Electronic Colloquium on Computational Complexity (ECCC), 2017
Simple doublyefficient interactive proof systems for locallycharacterizable sets.
Electronic Colloquium on Computational Complexity (ECCC), 2017
Overview of the doublyefficient interactive proof systems of RRR.
Electronic Colloquium on Computational Complexity (ECCC), 2017
On the doublyefficient interactive proof systems of GKR.
Electronic Colloquium on Computational Complexity (ECCC), 2017
Introduction to Property Testing.
Cambridge University Press, ISBN: 9781108135252, 2017
2016
Testing Bipartiteness of Graphs in Sublinear Time.
Encyclopedia of Algorithms, 2016
Testing Bipartiteness in the DenseGraph Model.
Encyclopedia of Algorithms, 2016
Estimating Simple Graph Parameters in Sublinear Time.
Encyclopedia of Algorithms, 2016
Twosided error proximity oblivious testing.
Random Struct. Algorithms, 2016
Universal Locally Verifiable Codes and 3Round Interactive Proofs of Proximity for CSP.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Deconstructing 1local expanders.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Reducing testing affine spaces to testing linearity.
Electronic Colloquium on Computational Complexity (ECCC), 2016
On Emulating Interactive Proofs with Public Coins.
Electronic Colloquium on Computational Complexity (ECCC), 2016
The uniform distribution is complete with respect to testing identity to a fixed distribution.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword.
Comput. Complex., 2016
2015
On Randomness Extraction in AC0.
Electronic Colloquium on Computational Complexity (ECCC), 2015
Proofs of Proximity for ContextFree Languages and ReadOnce Branching Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2015
Proofs of Proximity for ContextFree Languages and ReadOnce Branching Programs  (Extended Abstract).
Proceedings of the Automata, Languages, and Programming  42nd International Colloquium, 2015
2014
SuperPerfect ZeroKnowledge Proofs.
Electronic Colloquium on Computational Complexity (ECCC), 2014
Strong Locally Testable Codes with Relaxed Local Decoders.
Electronic Colloquium on Computational Complexity (ECCC), 2014
2013
A Short Tutorial of ZeroKnowledge.
Proceedings of the Secure MultiParty Computation, 2013
General Cryptographic Protocols: The Very Basics.
Proceedings of the Secure MultiParty Computation, 2013
Enhancements of Trapdoor Permutations.
J. Cryptology, 2013
More Constructions of Lossy and CorrelationSecure Trapdoor Functions.
J. Cryptology, 2013
On Derandomizing Algorithms that Err Extremely Rarely.
Electronic Colloquium on Computational Complexity (ECCC), 2013
On the Size of DepthThree Boolean Circuits for Computing Multilinear Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013
On SampleBased Testers.
Electronic Colloquium on Computational Complexity (ECCC), 2013
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2013
On Multiple Input Problems in Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2013
2012
Monotone Circuits: OneWay Functions versus Pseudorandom Generators.
Theory Comput., 2012
On intellectual and instrumental values in science.
SIGACT News, 2012
On struggle and competition in scientic fields.
SIGACT News, 2012
A theory of goaloriented communication.
J. ACM, 2012
On the (im)possibility of obfuscating programs.
J. ACM, 2012
The tensor product of two good codes is not necessarily robustly testable.
Inf. Process. Lett., 2012
On the possibilities and limitations of pseudodeterministic algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2012
TwoSided Error Proximity Oblivious Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2012
On the Effect of the Proximity Parameter on Property Testers.
Electronic Colloquium on Computational Complexity (ECCC), 2012
Finding Cycles and Trees in Sublinear Time.
Electronic Colloquium on Computational Complexity (ECCC), 2012
Invitation to complexity theory.
XRDS, 2012
Special issue from RANDOM'09: Editors' Foreword.
Comput. Complex., 2012
Hierarchy Theorems for Property Testing.
Comput. Complex., 2012
TwoSided Error Proximity Oblivious Testing  (Extended Abstract).
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012
2011
On the complexity of computational problems regarding distributions (a survey).
Electronic Colloquium on Computational Complexity (ECCC), 2011
InputOblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
Electronic Colloquium on Computational Complexity (ECCC), 2011
Two Comments on Targeted Canonical Derandomizers.
Electronic Colloquium on Computational Complexity (ECCC), 2011
Testing Graph BlowUp.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011
Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More).
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On the Circuit Complexity of Perfect Hashing.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Simplified Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On the Complexity of Computational Problems Regarding Distributions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
From Logarithmic Advice to SingleBit Advice.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On Testing Expansion in BoundedDegree Graphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On Yao's XORLemma.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On Constructing 11 OneWay Functions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Proximity Oblivious Testing and the Role of Invariances.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
CollisionFree Hashing from Lattice Problems.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Another Motivation for Reducing the Randomness Complexity of Algorithms.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Contemplations on Testing Graph Properties.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On Security Preserving Reductions  Revised Terminology.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Randomness and Computation.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Introduction to Testing Graph Properties.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
A Brief Introduction to Property Testing.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Basic Facts about Expander Graphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Average Case Complexity, Revisited.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Basing NonInteractive ZeroKnowledge on (Enhanced) Trapdoor Permutations: The State of the Art.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Bravely, Moderately: A Common Theme in Four Recent Works.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Short Locally Testable Codes and Proofs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
A Sample of Samplers: A Computational Perspective on Sampling.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Three XORLemmas  An Exposition.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Notes on Levin's Theory of AverageCase Complexity.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
In a World of P=BPP.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
A Candidate Counterexample to the Easy Cylinders Conjecture.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On the AverageCase Complexity of Property Testing.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Using the FGLSSReduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Candidate OneWay Functions Based on Expander Graphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Strong Proofs of Knowledge.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Finding the Shortest MoveSequence in the GraphGeneralized 15Puzzle Is NPHard.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
From Absolute Distinguishability to Positive Distinguishability.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Proving Computational Ability.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
Testing Graph BlowUp.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
2010
On Expected Probabilistic PolynomialTime Adversaries: A Suggestion for Restricted Definitions and Their Benefits.
J. Cryptology, 2010
Proximity Oblivious Testing and the Role of Invariances.
Electronic Colloquium on Computational Complexity (ECCC), 2010
In a World of P=BPP.
Electronic Colloquium on Computational Complexity (ECCC), 2010
Introduction to Testing Graph Properties.
Electronic Colloquium on Computational Complexity (ECCC), 2010
On Testing Computability by Small Width OBDDs.
Electronic Colloquium on Computational Complexity (ECCC), 2010
On The Randomness Complexity of Property Testing.
Comput. Complex., 2010
Erratum for: on basing oneway functions on NPhardness.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Proceedings of the Property Testing  Current Research and Surveys, 2010
Hierarchy Theorems for Property Testing.
Proceedings of the Property Testing  Current Research and Surveys, 2010
Introduction to Testing Graph Properties.
Proceedings of the Property Testing  Current Research and Surveys, 2010
Short Locally Testable Codes and Proofs: A Survey in Two Parts.
Proceedings of the Property Testing  Current Research and Surveys, 2010
The Program of the MiniWorkshop.
Proceedings of the Property Testing  Current Research and Surveys, 2010
A Brief Introduction to Property Testing.
Proceedings of the Property Testing  Current Research and Surveys, 2010
P, NP, and NPCompleteness: The Basics of Complexity Theory.
Cambridge University Press, ISBN: 9780511761355, 2010
2009
On our duties as scientists.
SIGACT News, 2009
A Candidate Counterexample to the Easy Cylinders Conjecture.
Electronic Colloquium on Computational Complexity (ECCC), 2009
From absolute distinguishability to positive distinguishability.
Electronic Colloquium on Computational Complexity (ECCC), 2009
2008
Computational complexity: a conceptual perspective.
SIGACT News, 2008
Probabilistic Proof Systems: A Primer.
Foundations and Trends in Theoretical Computer Science, 2008
On Proximity Oblivious Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2008
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Electronic Colloquium on Computational Complexity (ECCC), 2008
Preface to the Special Issue from Random'06.
Comput. Complex., 2008
Computational complexity  a conceptual perspective.
Cambridge University Press, ISBN: 9780511804106, 2008
2007
On the AverageCase Complexity of Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2007
Special Issue On Worstcase Versus Averagecase Complexity Editors' Foreword.
Comput. Complex., 2007
On Approximating the Average Distance Between Points.
Proceedings of the Approximation, 2007
2006
Special Issue on Randomness and Complexity.
SIAM J. Comput., 2006
SessionKey Generation Using Human Passwords Only.
J. Cryptology, 2006
Locally testable codes and PCPs of almostlinear length.
J. ACM, 2006
On PostModern Cryptography.
IACR Cryptol. ePrint Arch., 2006
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
Electronic Colloquium on Computational Complexity (ECCC), 2006
Lower bounds for linear locally decodable codes and private information retrieval.
Comput. Complex., 2006
On basing oneway functions on NPhardness.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
On Teaching the Basics of Complexity Theory.
Proceedings of the Theoretical Computer Science, 2006
On Promise Problems: A Survey.
Proceedings of the Theoretical Computer Science, 2006
2005
Foundations of Cryptography  A Primer.
Foundations and Trends in Theoretical Computer Science, 2005
Bravely, Moderately: A Common Theme in Four Recent Results
Electronic Colloquium on Computational Complexity (ECCC), 2005
Approximating Average Parameters of Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2005
On Promise Problems (a survey in memory of Shimon Even [19352004])
Electronic Colloquium on Computational Complexity (ECCC), 2005
Short Locally Testable Codes and Proofs (Survey)
Electronic Colloquium on Computational Complexity (ECCC), 2005
Contemplations on Testing Graph Properties.
Proceedings of the Sublinear Algorithms, 17.07.  22.07.2005, 2005
Short PCPs Verifiable in Polylogarithmic Time.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005
2004
The random oracle methodology, revisited.
J. ACM, 2004
The Power of Verification Queries in Message Authentication and Authenticated Encryption.
IACR Cryptol. ePrint Arch., 2004
From logarithmic advice to singlebit advice
Electronic Colloquium on Computational Complexity (ECCC), 2004
Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Electronic Colloquium on Computational Complexity (ECCC), 2004
On Estimating the Average Degree of a Graph
Electronic Colloquium on Computational Complexity (ECCC), 2004
The Foundations of Cryptography  Volume 2: Basic Applications.
Cambridge University Press, ISBN: 9780511721656, 2004
Pseudorandomness  Part I.
Proceedings of the Computational Complexity Theory., 2004
Preface to "Week Three: Randomness in Computation".
Proceedings of the Computational Complexity Theory., 2004
2003
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators.
J. Cryptology, 2003
Almost kwise independence versus kwise independence.
Inf. Process. Lett., 2003
On the randomoracle methodology as applied to lengthrestricted signature schemes.
IACR Cryptol. ePrint Arch., 2003
On the Implementation of Huge Random Objects.
Electronic Colloquium on Computational Complexity (ECCC), 2003
Bounds on 2Query Codeword Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2003
Cryptography and cryptographic protocols.
Distributed Comput., 2003
2002
On Chosen Ciphertext Security of Multiple Encryptions.
IACR Cryptol. ePrint Arch., 2002
ZeroKnowledge twenty years after its invention
Electronic Colloquium on Computational Complexity (ECCC), 2002
The GGM Construction does NOT yield Correlation Intractable Function Ensembles.
Electronic Colloquium on Computational Complexity (ECCC), 2002
Derandomization that is rarely wrong from short advice that is typically good
Electronic Colloquium on Computational Complexity (ECCC), 2002
On interactive proofs with a laconic prover.
Comput. Complex., 2002
Property Testing in Bounded Degree Graphs.
Algorithmica, 2002
ZeroKnowledge.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
ResettablySound ZeroKnowledge and its Applications.
IACR Cryptol. ePrint Arch., 2001
Using the FGLSSreduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.
Electronic Colloquium on Computational Complexity (ECCC), 2001
Universal Arguments and their Applications.
Electronic Colloquium on Computational Complexity (ECCC), 2001
Concurrent ZeroKnowledge With Timing, Revisited
Electronic Colloquium on Computational Complexity (ECCC), 2001
Three Theorems regarding Testing Graph Properties.
Electronic Colloquium on Computational Complexity (ECCC), 2001
The Foundations of Cryptography  Volume 1: Basic Techniques.
Cambridge University Press, ISBN: 9780511546891, 2001
2000
Learning Polynomials with Queries: The Highly Noisy Case.
SIAM J. Discret. Math., 2000
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
SIAM J. Comput., 2000
Preface.
J. Cryptology, 2000
On the Limits of Nonapproximability of Lattice Problems.
J. Comput. Syst. Sci., 2000
On Security Preserving Reductions  Revised Terminology.
IACR Cryptol. ePrint Arch., 2000
Candidate OneWay Functions Based on Expander Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2000
On Pseudorandomness with respect to Deterministic Observers.
Electronic Colloquium on Computational Complexity (ECCC), 2000
On Testing Expansion in BoundedDegree Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2000
Simplified derandomization of BPP using a hitting set generator.
Electronic Colloquium on Computational Complexity (ECCC), 2000
Testing Monotonicity.
Combinatorica, 2000
Resettable zeroknowledge (extended abstract).
Proceedings of the ThirtySecond Annual ACM Symposium on Theory of Computing, 2000
On Pseudorandomness with respect to Deterministic Observes.
Proceedings of the ICALP Workshops 2000, 2000
Pseudorandomness.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000
1999
Computational Indistinguishability: A Sample Hierarchy.
J. Comput. Syst. Sci., 1999
The Graph Clustering Problem has a Perfect ZeroKnowledge Interactive Proof.
Inf. Process. Lett., 1999
Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.
Inf. Process. Lett., 1999
Resettable ZeroKnowledge.
Electronic Colloquium on Computational Complexity (ECCC), 1999
Interleaved ZeroKnowledge in the PublicKey Model.
Electronic Colloquium on Computational Complexity (ECCC), 1999
Improved Testing Algorithms for Monotonicity.
Electronic Colloquium on Computational Complexity (ECCC), 1999
Can Statistical Zero Knowledge be made NonInteractive? or On the Relationship of SZK and NISZK
Electronic Colloquium on Computational Complexity (ECCC), 1999
A Sublinear Bipartiteness Tester for Bounded Degree Graphs.
Combinatorica, 1999
Quantifying Knowledge Complexity.
Comput. Complex., 1999
Improved Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Randomization, 1999
Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier.
Proceedings of the Advances in Cryptology, 1999
1998
Computational Indistinguishability: Algorithms vs. Circuits.
Theor. Comput. Sci., 1998
FaultTolerant Computation in the Full Information Model.
SIAM J. Comput., 1998
Free Bits, PCPs, and NonapproximabilityTowards Tight Results.
SIAM J. Comput., 1998
Efficient approximation of product distributions.
Random Struct. Algorithms, 1998
Property Testing and its Connection to Learning and Approximation.
J. ACM, 1998
Private Information Retrieval.
J. ACM, 1998
On the Complexity of Interactive Proofs with Bounded Communication.
Inf. Process. Lett., 1998
On the possibility of basing Cryptography on the assumption that P ≠ NP.
IACR Cryptol. ePrint Arch., 1998
Deterministic Amplification of Space Bounded Probabilistic Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 1998
Comparing Entropies in Statistical ZeroKnowledge with Applications to the Structure of SZK
Electronic Colloquium on Computational Complexity (ECCC), 1998
Chinese Remaindering with Errors
Electronic Colloquium on Computational Complexity (ECCC), 1998
Uniform Generation of NPwitnesses using an NPoracle.
Electronic Colloquium on Computational Complexity (ECCC), 1998
The Graph Clustering Problem has a Perfect ZeroKnowledge Proof
Electronic Colloquium on Computational Complexity (ECCC), 1998
HonestVerifier Statistical ZeroKnowledge Equals General Statistical ZeroKnowledge.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
The Random Oracle Methodology, Revisited (Preliminary Version).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Testing Monotonicity.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
Modern Cryptography, Probabilistic Proofs and Pseudorandomness.
Algorithms and Combinatorics 17, Springer, ISBN: 9783540647669, 1998
1997
Theory of computing: a scientific perspective (extended abstract).
SIGACT News, 1997
On Universal Learning Algorithms.
Inf. Process. Lett., 1997
SelfDelegation with Controlled Propagation  or  What If You Lose Your Laptop.
IACR Cryptol. ePrint Arch., 1997
A Probabilistic ErrorCorrecting Scheme.
IACR Cryptol. ePrint Arch., 1997
Notes on Levin's Theory of AverageCase Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 1997
Combinatorial Property Testing (a survey).
Electronic Colloquium on Computational Complexity (ECCC), 1997
Another proof that BPP subseteq PH (and more).
Electronic Colloquium on Computational Complexity (ECCC), 1997
On the Limits of NonApproximability of Lattice Problems
Electronic Colloquium on Computational Complexity (ECCC), 1997
Computational Sample Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1997
A Sample of Samplers  A Computational Perspective on Sampling (survey).
Electronic Colloquium on Computational Complexity (ECCC), 1997
Eliminating Decryption Errors in the AjtaiDwork Cryptosystem.
Electronic Colloquium on Computational Complexity (ECCC), 1997
On the Foundations of Modern Cryptography.
Proceedings of the Advances in Cryptology, 1997
1996
The future of computational complexity theory: part I.
SIGACT News, 1996
On the Composition of ZeroKnowledge Proof Systems.
SIAM J. Comput., 1996
How to Construct ConstantRound ZeroKnowledge Proof Systems for NP.
J. Cryptology, 1996
OnLine/OffLine Digital Signatures.
J. Cryptology, 1996
Software Protection and Simulation on Oblivious RAMs.
J. ACM, 1996
PublicKey Cryptosystems from Lattice Reduction Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996
The Graph Clustering Problem has a Perfect ZeroKnowledge Proof.
Electronic Colloquium on Computational Complexity (ECCC), 1996
A Combinatorial Consistency Lemma with application to the PCP Theorem
Electronic Colloquium on Computational Complexity (ECCC), 1996
CollisionFree Hashing from Lattice Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996
On the Circuit Complexity of Perfect Hashing
Electronic Colloquium on Computational Complexity (ECCC), 1996
On the Message Complexity of Interactive Proof Systems
Electronic Colloquium on Computational Complexity (ECCC), 1996
Theory of Computing: A Scientific Perspective.
ACM Comput. Surv., 1996
Adaptively Secure MultiParty Computation.
Proceedings of the TwentyEighth Annual ACM Symposium on the Theory of Computing, 1996
1995
Lower Bounds for Sampling Algorithms for Estimating the Average.
Inf. Process. Lett., 1995
Three XORLemmas  An Exposition
Electronic Colloquium on Computational Complexity (ECCC), 1995
On Yao's XORLemma
Electronic Colloquium on Computational Complexity (ECCC), 1995
On Constructing 11 OneWay Functions
Electronic Colloquium on Computational Complexity (ECCC), 1995
Free Bits, PCP and NonApproximability  Towards Tight Results
Electronic Colloquium on Computational Complexity (ECCC), 1995
Incremental cryptography and application to virus protection.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
Free Bits, PCPs and NonApproximability  Towards Tight Results.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995
Honest Verifier vs Dishonest Verifier in Public Coin ZeroKnowledge Proofs.
Proceedings of the Advances in Cryptology, 1995
1994
A taxonomy of proof systems (part 2).
SIGACT News, 1994
Definitions and Properties of ZeroKnowledge Proof Systems.
J. Cryptology, 1994
The Random Oracle Hypothesis Is False.
J. Comput. Syst. Sci., 1994
Probabilistic Proof Systems (A Survey)
Electronic Colloquium on Computational Complexity (ECCC), 1994
Computational Complexity and Knowledge Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1994
Tiny Families of Functions with Random Properties: A QualitySize Tradeoff for Hashing
Electronic Colloquium on Computational Complexity (ECCC), 1994
Tiny families of functions with random properties (preliminary version): a qualitysize tradeoff for hashing.
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
Computational complexity and knowledge complexity (extended abstract).
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
Incremental Cryptography: The Case of Hashing and Signing.
Proceedings of the Advances in Cryptology, 1994
1993
A taxonomy of proof systems (part 1).
SIGACT News, 1993
On the Existence of Pseudorandom Generators.
SIAM J. Comput., 1993
Addendum to "Simple Construction of Almost kwise Independent Random Variables".
Random Struct. Algorithms, 1993
A Perfect ZeroKnowledge Proof System for a Problem Equivalent to the Discrete Logarithm.
J. Cryptology, 1993
A UniformComplexity Treatment of Encryption and ZeroKnowledge.
J. Cryptology, 1993
Bounds on Tradeoffs Between Randomness and Communication Complexity.
Comput. Complex., 1993
Randomness in Interactive Proofs.
Comput. Complex., 1993
Asynchronous secure computation.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
1992
Critique of some trends in the TCS community in light of two controversies.
SIGACT News, 1992
Sparse Pseudorandom Distributions.
Random Struct. Algorithms, 1992
Simple Construction of Almost kwise Independent Random Variables.
Random Struct. Algorithms, 1992
On the Theory of Average Case Complexity.
J. Comput. Syst. Sci., 1992
On the TimeComplexity of Broadcast in Multihop Radio Networks: An Exponential Gap Between Determinism and Randomization.
J. Comput. Syst. Sci., 1992
Approximations of General Independent Distributions
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
On the Complexity of Global Computation in the Presence of Link Failures: The Case of UniDirectional Faults.
Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992
Towards a Computational Theory of Statistical Tests (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
On Defining Proofs of Knowledge.
Proceedings of the Advances in Cryptology, 1992
1991
Proofs that Yield Nothing But Their Validity for All Languages in NP Have ZeroKnowledge Proof Systems.
J. ACM, 1991
On the Complexity of Computation in the Presence of Link Failures: The Case of a Ring.
Distributed Comput., 1991
Efficient Emulation of SingleHop Radio Network with Collision Detection on MultiHop Radio Network with no Collision Detection.
Distributed Comput., 1991
Faulttolerant Computation in the Full Information Model (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
1990
A TradeOff between Information and Communication in Broadcast Protocols
J. ACM, April, 1990
A fair protocol for signing contracts.
IEEE Trans. Inf. Theory, 1990
The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols.
Inf. Process. Lett., 1990
A Note on Computational Indistinguishability.
Inf. Process. Lett., 1990
On the number of monochromatic close pairs of beads in a rosary.
Discret. Math., 1990
An Improved Parallel Algorithm for Integer GCD.
Algorithmica, 1990
A Quantitative Approach to Dynamic Networks.
Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990
Security Preserving Amplification of Hardness
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
Simple Constructions of Almost kWise Independent Random Variables
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
1989
On the power of twopoint based sampling.
J. Complex., 1989
On Completeness and Soundness in Interactive Proof Systems.
Advances in Computing Research, 1989
A HardCore Predicate for all OneWay Functions
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Source to Destination Communication in the Presence of Faults.
Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, 1989
OnLine/OffLine Digital Schemes.
Proceedings of the Advances in Cryptology, 1989
On the Theory of Average Case Complexity (abstract).
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989
1988
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity.
SIAM J. Comput., 1988
RSA and Rabin Functions: Certain Parts are as Hard as the Whole.
SIAM J. Comput., 1988
On the Existence of Pseudorandom Generators (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988
A Perfect ZeroKnowledge Proof for a Problem Equivalent to Discrete Logarithm.
Proceedings of the Advances in Cryptology, 1988
Everything Provable is Provable in ZeroKnowledge.
Proceedings of the Advances in Cryptology, 1988
A Tradeoff between Information and Communication in Broadcast Protocols.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988
1987
Electing a Leader in a Ring with Link Failures.
Acta Informatica, 1987
How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987
Towards a Theory of Software Protection and Simulation by Oblivious RAMs
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987
On the TimeComplexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization.
Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987
Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987
How to Solve any Protocol Problem  An Efficiency Improvement.
Proceedings of the Advances in Cryptology, 1987
1986
How to construct random functions.
J. ACM, 1986
The Effect of Link Failures on Computations in Asynchronous Rings.
Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986
Proofs that Release Minimum Knowledge.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986
Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
How to Prove all NPStatements in ZeroKnowledge, and a Methodology of Cryptographic Protocol Design.
Proceedings of the Advances in Cryptology, 1986
Towards a Theory of Software Protection.
Proceedings of the Advances in Cryptology, 1986
Two Remarks Concerning the GoldwasserMicaliRivest Signature Scheme.
Proceedings of the Advances in Cryptology, 1986
1985
On the Power of Cascade Ciphers
ACM Trans. Comput. Syst., 1985
A Randomized Protocol for Signing Contracts.
Commun. ACM, 1985
A Fair Protocol for Signing Contracts (Extended Abstract).
Proceedings of the Automata, 1985
The Bit Extraction Problem of tResilient Functions (Preliminary Version)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
On the Security of PingPong Protocols when Implemented using the RSA.
Proceedings of the Advances in Cryptology, 1985
The Bit Security of Modular Squaring Given Partial Factorization of the Modulos.
Proceedings of the Advances in Cryptology, 1985
1984
Correction to 'DESlike functions can generate the alternating group' (Nov 83 863865).
IEEE Trans. Inf. Theory, 1984
On the npcompleteness of certain network testing problems.
Networks, 1984
How to Construct Random Functions (Extended Abstract)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
On Concurrent Identification Protocols.
Proceedings of the Advances in Cryptology: Proceedings of EUROCRYPT 84, 1984
On the Number of CloseandEqual Pairs of Bits in a String.
Proceedings of the Advances in Cryptology: Proceedings of EUROCRYPT 84, 1984
On the Cryptographic Applications of Random Functions.
Proceedings of the Advances in Cryptology, 1984
RSA/Rabin Least Significant Bits are 1/2 + 1/(poly(log N)) Secure.
Proceedings of the Advances in Cryptology, 1984
1983
DESlike functions can generate the alternating group.
IEEE Trans. Inf. Theory, 1983
On the Security of MultiParty PingPong Protocols
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
Electronic Wallet.
Proceedings of the Advances in Cryptology, 1983
A Simple Protocol for Signing Contracts.
Proceedings of the Advances in Cryptology, 1983
1981
The MinimumLength Generator Sequence Problem is NPHard.
J. Algorithms, 1981