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

at zbmath.org

at viaf.org

at orcid.org

at id.loc.gov

at dnb.info

at isni.org

at dl.acm.org
On csauthors.net:
Bibliography
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
Testing graphs in vertexdistributionfree models.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
Every Set in P Is Strongly Testable Under a Suitable Encoding.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
The Subgraph Testing Model.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
2018
Proofs of proximity for contextfree languages and readonce branching programs.
Inf. Comput., 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
Flexible models for testing graph properties.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Hierarchy Theorems for Testing Properties in SizeOblivious Query Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Universal Locally Testable Codes.
Chicago J. Theor. Comput. Sci., 2018
Simple DoublyEfficient Interactive Proof Systems for LocallyCharacterizable Sets.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 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 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
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
Universal Locally Testable Codes.
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.
Computational Complexity, 2016
Matrix rigidity of random toeplitz matrices.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
2015
InputOblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
TOCT, 2015
Proofs of Proximity for ContextFree Languages and ReadOnce Branching Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2015
On SampleBased Testers.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015
Proofs of Proximity for ContextFree Languages and ReadOnce Branching Programs  (Extended Abstract).
Proceedings of the Automata, Languages, and Programming  42nd International Colloquium, 2015
On Randomness Extraction in AC0.
Proceedings of the 30th Conference on Computational Complexity, 2015
Strong Locally Testable Codes with Relaxed Local Decoders.
Proceedings of the 30th Conference on Computational Complexity, 2015
2014
Finding cycles and trees in sublinear time.
Random Struct. Algorithms, 2014
SuperPerfect ZeroKnowledge Proofs.
Electronic Colloquium on Computational Complexity (ECCC), 2014
On derandomizing algorithms that err extremely rarely.
Proceedings of the Symposium on Theory of Computing, 2014
On Learning and Testing Dynamic Environments.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014
On Multiple Input Problems in Property Testing.
Proceedings of the Approximation, 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
On the Size of DepthThree Boolean Circuits for Computing Multilinear Functions.
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 the possibilities and limitations of pseudodeterministic algorithms.
Proceedings of the Innovations in Theoretical Computer Science, 2013
2012
Monotone Circuits: OneWay Functions versus Pseudorandom Generators.
Theory of Computing, 2012
On intellectual and instrumental values in science.
SIGACT News, 2012
On struggle and competition in scientic fields.
SIGACT News, 2012
The tensor product of two good codes is not necessarily robustly testable.
Inf. Process. Lett., 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.
ACM Crossroads, 2012
Special issue from RANDOM'09: Editors' Foreword.
Computational Complexity, 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
Enhancements of Trapdoor Permutations.
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
Monotone Circuits: OneWay Functions versus Pseudorandom Generators.
Electronic Colloquium on Computational Complexity (ECCC), 2011
Two Comments on Targeted Canonical Derandomizers.
Electronic Colloquium on Computational Complexity (ECCC), 2011
A theory of goaloriented communication.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011
Proximity Oblivious Testing and the Role of Invariances.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 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
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
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
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
Erratum for: on basing oneway functions on NPhardness.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 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
More Constructions of Lossy and CorrelationSecure Trapdoor Functions.
Proceedings of the Public Key Cryptography, 2010
On Testing Computability by Small Width OBDDs.
Proceedings of the Approximation, 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
On proximity oblivious testing.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Proceedings of the Approximation, 2009
Hierarchy Theorems for Property Testing.
Proceedings of the Approximation, 2009
2008
Computational complexity: a conceptual perspective.
SIGACT News, 2008
Probabilistic Proof Systems: A Primer.
Foundations and Trends in Theoretical Computer Science, 2008
Preface to the Special Issue from Random'06.
Computational Complexity, 2008
Computational complexity  a conceptual perspective.
Cambridge University Press, ISBN: 9780511804106, 2008
2007
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable.
Electronic Colloquium on Computational Complexity (ECCC), 2007
On the AverageCase Complexity of Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2007
Special Issue On Worstcase Versus Averagecase Complexity Editors' Foreword.
Computational Complexity, 2007
On Expected Probabilistic PolynomialTime Adversaries: A Suggestion for Restricted Definitions and Their Benefits.
Proceedings of the Theory of Cryptography, 4th Theory of Cryptography Conference, 2007
On the Randomness Complexity of Property Testing.
Proceedings of the Approximation, 2007
On Approximating the Average Distance Between Points.
Proceedings of the Approximation, 2007
2006
Special Issue on Randomness and Complexity.
SIAM J. Comput., 2006
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.
SIAM J. Comput., 2006
On PostModern Cryptography.
IACR Cryptology ePrint Archive, 2006
On Expected Probabilistic PolynomialTime Adversaries  A suggestion for restricted definitions and their benefits.
IACR Cryptology ePrint Archive, 2006
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
IACR Cryptology ePrint Archive, 2006
On Expected Probabilistic PolynomialTime Adversaries  A suggestion for restricted definitions and their benefits.
Electronic Colloquium on Computational Complexity (ECCC), 2006
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
Electronic Colloquium on Computational Complexity (ECCC), 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
Concurrent ZeroKnowledge with Timing, Revisited.
Proceedings of the Theoretical Computer Science, 2006
Approximating Average Parameters of Graphs.
Proceedings of the Approximation, 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
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
Approximating Average Parameters of Graphs.
Proceedings of the Sublinear Algorithms, 17.07.  22.07.2005, 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
Preface.
J. Cryptology, 2004
The random oracle methodology, revisited.
J. ACM, 2004
The Power of Verification Queries in Message Authentication and Authenticated Encryption.
IACR Cryptology ePrint Archive, 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
On the RandomOracle Methodology as Applied to LengthRestricted Signature Schemes.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004
Robust pcps of proximity, shorter pcps and applications to coding.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 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
Cryptography and cryptographic protocols.
Distributed Computing, 2003
Bounds on 2Query Codeword Testing.
Proceedings of the Approximation, 2003
On the Implementation of Huge Random Objects.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
2002
On Chosen Ciphertext Security of Multiple Encryptions.
IACR Cryptology ePrint Archive, 2002
ZeroKnowledge twenty years after its invention.
IACR Cryptology ePrint Archive, 2002
The GGM Construction does NOT yield Correlation Intractable Function Ensembles.
IACR Cryptology ePrint Archive, 2002
ZeroKnowledge twenty years after its invention
Electronic Colloquium on Computational Complexity (ECCC), 2002
Locally Testable Codes and PCPs of AlmostLinear Length
Electronic Colloquium on Computational Complexity (ECCC), 2002
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators
Electronic Colloquium on Computational Complexity (ECCC), 2002
Almost kwise independence versus kwise independence.
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
Concurrent zeroknowledge with timing, revisited.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002
Locally Testable Codes and PCPs of AlmostLinear Length.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
ZeroKnowledge.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002
Universal Arguments and their Applications.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002
2001
Using the FGLSSreduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.
Electronic Colloquium on Computational Complexity (ECCC), 2001
Concurrent ZeroKnowledge With Timing, Revisited
Electronic Colloquium on Computational Complexity (ECCC), 2001
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
Electronic Colloquium on Computational Complexity (ECCC), 2001
On the (Im)possibility of Obfuscating Programs
Electronic Colloquium on Computational Complexity (ECCC), 2001
On Interactive Proofs with a Laconic Prover
Electronic Colloquium on Computational Complexity (ECCC), 2001
On Interactive Proofs with a Laconic Prover.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001
Three Theorems Regarding Testing Graph Properties.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
ResettablySound ZeroKnowledge and its Applications.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
SessionKey Generation Using Human Passwords Only.
Proceedings of the Advances in Cryptology, 2001
On the (Im)possibility of Obfuscating Programs.
Proceedings of the Advances in Cryptology, 2001
The Foundations of Cryptography  Volume 1: Basic Techniques.
Cambridge University Press, ISBN: 9780511546891, 2001
2000
Preface.
J. Cryptology, 2000
On the Limits of Nonapproximability of Lattice Problems.
J. Comput. Syst. Sci., 2000
Uniform Generation of NPWitnesses Using an NPOracle.
Inf. Comput., 2000
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators.
IACR Cryptology ePrint Archive, 2000
Candidate OneWay Functions Based on Expander Graphs.
IACR Cryptology ePrint Archive, 2000
On Security Preserving Reductions  Revised Terminology.
IACR Cryptology ePrint Archive, 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
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
Interleaved ZeroKnowledge in the PublicKey Model.
IACR Cryptology ePrint Archive, 1999
Resettable ZeroKnowledge.
IACR Cryptology ePrint Archive, 1999
Resettable ZeroKnowledge.
Electronic Colloquium on Computational Complexity (ECCC), 1999
Interleaved ZeroKnowledge in the PublicKey Model.
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
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.
Electronic Colloquium on Computational Complexity (ECCC), 1999
A Sublinear Bipartiteness Tester for Bounded Degree Graphs.
Combinatorica, 1999
Quantifying Knowledge Complexity.
Computational Complexity, 1999
Chinese Remaindering with Errors.
Proceedings of the ThirtyFirst Annual ACM Symposium on Theory of Computing, 1999
Improved Derandomization of BPP Using a Hitting Set Generator.
Proceedings of the Randomization, 1999
Improved Testing Algorithms for Monotonicity.
Proceedings of the Randomization, 1999
Can Statistical Zero Knowledge Be Made Noninteractive? or On the Relationship of SZK and NISZK.
Proceedings of the Advances in Cryptology, 1999
Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier.
Proceedings of the Advances in Cryptology, 1999
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999
Deterministic Amplification of SpaceBounded Probabilistic Algorithms.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999
1998
Computational Indistinguishability: Algorithms vs. Circuits.
Theor. Comput. Sci., 1998
Computational Complexity and Knowledge Complexity.
SIAM J. Comput., 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
Private Information Retrieval.
J. ACM, 1998
On the Complexity of Interactive Proofs with Bounded Communication.
Inf. Process. Lett., 1998
The Graph Clustering Problem has a Perfect ZeroKnowledge Proof.
IACR Cryptology ePrint Archive, 1998
On the possibility of basing Cryptography on the assumption that P ≠ NP.
IACR Cryptology ePrint Archive, 1998
The Random Oracle Methodology, Revisited.
IACR Cryptology ePrint Archive, 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
Learning Polynomials with Queries  The Highly Noisy Case.
Electronic Colloquium on Computational Complexity (ECCC), 1998
Uniform Generation of NPwitnesses using an NPoracle.
Electronic Colloquium on Computational Complexity (ECCC), 1998
Computational Indistinguishability: A Sample Hierarchy
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
On the Limits of NonApproximability of Lattice Problems.
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
SelfDelegation with Controlled Propagation  or  What If You Lose Your Laptop.
Proceedings of the Advances in Cryptology, 1998
Computational Indistinguishability: A Sample Hierarchy.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 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
Tiny families of functions with random properties: A qualitysize tradeoff for hashing.
Random Struct. Algorithms, 1997
On Universal Learning Algorithms.
Inf. Process. Lett., 1997
A Probabilistic ErrorCorrecting Scheme.
IACR Cryptology ePrint Archive, 1997
Notes on Levin's Theory of AverageCase Complexity.
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
Property Testing in Bounded Degree Graphs.
Proceedings of the TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Probabilistic Proof Systems  A Survey.
Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997
Combinatorial property testing (a survey).
Proceedings of the Randomization Methods in Algorithm Design, 1997
PublicKey Cryptosystems from Lattice Reduction Problems.
Proceedings of the Advances in Cryptology, 1997
Eliminating Decryption Errors in the AjtaiDwork Cryptosystem.
Proceedings of the Advances in Cryptology, 1997
On the Foundations of Modern Cryptography.
Proceedings of the Advances in Cryptology, 1997
Computational Sample Complexity.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997
1996
The future of computational complexity theory: part I.
SIGACT News, 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
CollisionFree Hashing from Lattice Problems.
IACR Cryptology ePrint Archive, 1996
The Graph Clustering Problem has a Perfect ZeroKnowledge Proof.
IACR Cryptology ePrint Archive, 1996
Computational Indistinguishability  Algorithms vs. Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 1996
Property Testing and its connection to Learning and Approximation
Electronic Colloquium on Computational Complexity (ECCC), 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
Property Testing and Its Connection to Learning and Approximation.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 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
Learning Polynomials with Queries: The Highly Noisy Case.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995
Private Information Retrieval.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 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
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.
Computational Complexity, 1993
Randomness in Interactive Proofs.
Computational Complexity, 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
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 Computing, 1991
Quantifying Knowledge Complexity
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 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. Information 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.
Discrete Mathematics, 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
On the Composition of ZeroKnowledge Proof Systems.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990
Security Preserving Amplification of Hardness
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
Bounds on Tradeoffs between Randomness and Communication Complexity
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
Randomness in Interactive Proofs
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. Complexity, 1989
On Completeness and Soundness in Interactive Proof Systems.
Advances in Computing Research, 1989
Efficient Emulation of SingleHop Radio Network with Collision Detection on MultiHop Radio Network with no Collision Detection.
Proceedings of the Distributed Algorithms, 1989
A HardCore Predicate for all OneWay Functions
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
On the Theory of Average Case Complexity
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
Sparse Pseudorandom Distributions.
Proceedings of the Advances in Cryptology, 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
On the Existence of Pseudorandom Generators.
Proceedings of the Advances in Cryptology, 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 Inf., 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 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. Information 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. Information 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
On the Power of Cascade Ciphers.
Proceedings of the Advances in Cryptology, 1983
A Simple Protocol for Signing Contracts.
Proceedings of the Advances in Cryptology, 1983
1982
A Randomized Protocol for Signing Contracts.
Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982
On the Security of MultiParty PingPong Protocols.
Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982
1981
The MinimumLength Generator Sequence Problem is NPHard.
J. Algorithms, 1981