Oded Goldreich

According to our database1, Oded Goldreich authored at least 360 papers between 1981 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2020
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy.
Proceedings of the Computational Complexity and Property Testing, 2020

Pseudo-mixing Time of Random Walks.
Proceedings of the Computational Complexity and Property Testing, 2020

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.
Proceedings of the Computational Complexity and Property Testing, 2020

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
Proceedings of the Computational Complexity and Property Testing, 2020

Super-Perfect Zero-Knowledge Proofs.
Proceedings of the Computational Complexity and Property Testing, 2020

Constant-Round Interactive Proof Systems for AC0[2] and NC1.
Proceedings of the Computational Complexity and Property Testing, 2020

Worst-Case to Average-Case 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 1-Local 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) Polynomial-Size Monotone Formula for Majority.
Proceedings of the Computational Complexity and Property Testing, 2020

One-Sided 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 AN-complexity of multilinear functions.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Testing Isomorphism in the Bounded-Degree 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

Multi-pseudodeterministic algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Pseudo-Mixing 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 Bounded-Degree Graph Model.
CoRR, 2019

Hierarchy Theorems for Testing Properties in Size-Oblivious 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 Doubly-Efficient Interactive Proof Systems.
Foundations and Trends in Theoretical Computer Science, 2018

Constant-round interactive proof systems for AC0[2] and NC1.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Counting t-cliques: Worst-case to average-case 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 Vertex-Distribution-Free 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 t-Cliques: Worst-Case to Average-Case 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 Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Worst-case to Average-case reductions for subclasses of P.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Simple doubly-efficient interactive proof systems for locally-characterizable sets.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Overview of the doubly-efficient interactive proof systems of RRR.
Electronic Colloquium on Computational Complexity (ECCC), 2017

On the doubly-efficient 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 Dense-Graph Model.
Encyclopedia of Algorithms, 2016

Estimating Simple Graph Parameters in Sublinear Time.
Encyclopedia of Algorithms, 2016

Two-sided error proximity oblivious testing.
Random Struct. Algorithms, 2016

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Deconstructing 1-local 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 Context-Free Languages and Read-Once Branching Programs.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract).
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Super-Perfect Zero-Knowledge 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 Zero-Knowledge.
Proceedings of the Secure Multi-Party Computation, 2013

General Cryptographic Protocols: The Very Basics.
Proceedings of the Secure Multi-Party Computation, 2013

Enhancements of Trapdoor Permutations.
J. Cryptology, 2013

More Constructions of Lossy and Correlation-Secure Trapdoor Functions.
J. Cryptology, 2013

On Derandomizing Algorithms that Err Extremely Rarely.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

On Sample-Based 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: One-Way 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 goal-oriented 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

Two-Sided 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

Two-Sided 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

Input-Oblivious 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 Blow-Up.
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 Single-Bit Advice.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Testing Expansion in Bounded-Degree Graphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Yao's XOR-Lemma.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Constructing 1-1 One-Way 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

Collision-Free 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 Non-Interactive Zero-Knowledge 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 XOR-Lemmas - 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 Average-Case 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 Average-Case 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 FGLSS-Reduction 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 One-Way 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 Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard.
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 Blow-Up.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
On Expected Probabilistic Polynomial-Time 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 one-way functions on NP-hardness.
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 Mini-Workshop.
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 NP-Completeness: 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 Average-Case Complexity of Property Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Special Issue On Worst-case Versus Average-case 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

Session-Key Generation Using Human Passwords Only.
J. Cryptology, 2006

Locally testable codes and PCPs of almost-linear length.
J. ACM, 2006

On Post-Modern 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 one-way functions on NP-hardness.
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 [1935-2004])
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 single-bit 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 k-wise independence versus k-wise independence.
Inf. Process. Lett., 2003

On the random-oracle methodology as applied to length-restricted signature schemes.
IACR Cryptol. ePrint Arch., 2003

On the Implementation of Huge Random Objects.
Electronic Colloquium on Computational Complexity (ECCC), 2003

Bounds on 2-Query 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

Zero-Knowledge 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

Zero-Knowledge.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
Resettably-Sound Zero-Knowledge and its Applications.
IACR Cryptol. ePrint Arch., 2001

Using the FGLSS-reduction 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 Zero-Knowledge 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 One-Way 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 Bounded-Degree 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 zero-knowledge (extended abstract).
Proceedings of the Thirty-Second 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 Zero-Knowledge Interactive Proof.
Inf. Process. Lett., 1999

Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.
Inf. Process. Lett., 1999

Resettable Zero-Knowledge.
Electronic Colloquium on Computational Complexity (ECCC), 1999

Interleaved Zero-Knowledge in the Public-Key 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 Non-Interactive? 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

Fault-Tolerant Computation in the Full Information Model.
SIAM J. Comput., 1998

Free Bits, PCPs, and Nonapproximability-Towards 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 Zero-Knowledge 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 NP-witnesses using an NP-oracle.
Electronic Colloquium on Computational Complexity (ECCC), 1998

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
Electronic Colloquium on Computational Complexity (ECCC), 1998

Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
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: 978-3-540-64766-9, 1998

1997
Theory of computing: a scientific perspective (extended abstract).
SIGACT News, 1997

On Universal Learning Algorithms.
Inf. Process. Lett., 1997

Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop.
IACR Cryptol. ePrint Arch., 1997

A Probabilistic Error-Correcting Scheme.
IACR Cryptol. ePrint Arch., 1997

Notes on Levin's Theory of Average-Case 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 Non-Approximability 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 Ajtai-Dwork 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 Zero-Knowledge Proof Systems.
SIAM J. Comput., 1996

How to Construct Constant-Round Zero-Knowledge Proof Systems for NP.
J. Cryptology, 1996

On-Line/Off-Line Digital Signatures.
J. Cryptology, 1996

Software Protection and Simulation on Oblivious RAMs.
J. ACM, 1996

Public-Key Cryptosystems from Lattice Reduction Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996

The Graph Clustering Problem has a Perfect Zero-Knowledge 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

Collision-Free 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 Multi-Party Computation.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995
Lower Bounds for Sampling Algorithms for Estimating the Average.
Inf. Process. Lett., 1995

Three XOR-Lemmas - An Exposition
Electronic Colloquium on Computational Complexity (ECCC), 1995

On Yao's XOR-Lemma
Electronic Colloquium on Computational Complexity (ECCC), 1995

On Constructing 1-1 One-Way Functions
Electronic Colloquium on Computational Complexity (ECCC), 1995

Free Bits, PCP and Non-Approximability - Towards Tight Results
Electronic Colloquium on Computational Complexity (ECCC), 1995

Incremental cryptography and application to virus protection.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Free Bits, PCPs and Non-Approximability - Towards Tight Results.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs.
Proceedings of the Advances in Cryptology, 1995

1994
A taxonomy of proof systems (part 2).
SIGACT News, 1994

Definitions and Properties of Zero-Knowledge 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 Quality-Size Trade-off for Hashing
Electronic Colloquium on Computational Complexity (ECCC), 1994

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Computational complexity and knowledge complexity (extended abstract).
Proceedings of the Twenty-Sixth 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 k-wise Independent Random Variables".
Random Struct. Algorithms, 1993

A Perfect Zero-Knowledge Proof System for a Problem Equivalent to the Discrete Logarithm.
J. Cryptology, 1993

A Uniform-Complexity Treatment of Encryption and Zero-Knowledge.
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 Twenty-Fifth 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 k-wise Independent Random Variables.
Random Struct. Algorithms, 1992

On the Theory of Average Case Complexity.
J. Comput. Syst. Sci., 1992

On the Time-Complexity of Broadcast in Multi-hop 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 Uni-Directional 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 Zero-Knowledge 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 Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.
Distributed Comput., 1991

Fault-tolerant Computation in the Full Information Model (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
A Trade-Off 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 k-Wise Independent Random Variables
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
On the power of two-point based sampling.
J. Complex., 1989

On Completeness and Soundness in Interactive Proof Systems.
Advances in Computing Research, 1989

A Hard-Core Predicate for all One-Way 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

On-Line/Off-Line 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 Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm.
Proceedings of the Advances in Cryptology, 1988

Everything Provable is Provable in Zero-Knowledge.
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 Time-Complexity 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 NP-Statements in Zero-Knowledge, 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 Goldwasser-Micali-Rivest 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 t-Resilient 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 Ping-Pong 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 'DES-like functions can generate the alternating group' (Nov 83 863-865).
IEEE Trans. Inf. Theory, 1984

On the np-completeness 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 Close-and-Equal 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
DES-like functions can generate the alternating group.
IEEE Trans. Inf. Theory, 1983

On the Security of Multi-Party Ping-Pong 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 Minimum-Length Generator Sequence Problem is NP-Hard.
J. Algorithms, 1981


  Loading...