Oded Goldreich

567 papers A* 95A 20B 3Journal 311Unranked 27
YearRankTypeTitle / Venue / Authors
2025 J jnl
Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Roei Tell
2025 — book
Computational Complexity and Local Algorithms - On the Interplay Between Randomness and Computation
Computational Complexity and Local Algorithms
Oded Goldreich
2025 A conf
Doubly Sub-Linear Interactive Proofs of Proximity.
ITCS
Noga Amir, Oded Goldreich, Guy N. Rothblum
2025 J jnl
Expansion without Connectivity: A Property Testing Perspective.
Electron. Colloquium Comput. Complex.
Irit Dinur, Oded Goldreich
2025 J jnl
Interactive proof systems for FARNESS.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tal Herman, Guy N. Rothblum
2025 J jnl
Location-Invariant Properties of Functions versus Properties of Distributions: United in Testing but Separated in Verification.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Guy N. Rothblum
2025 — ch.
Multi-pseudodeterministic Algorithms.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Coarse and Fine Approximate Counting of t-Cliques.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Counting t-Cliques Mod 2.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Defining PPT-Search Problems.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Locally-Characterized Expander Graphs (A Survey).
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Parallel Repetition of Interactive Proof Systems.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Properties that are Non-trivial to Test.
Computational Complexity and Local Algorithms
Nader H. Bshouty, Oded Goldreich
2025 — ch.
On Testing Asymmetry in the Bounded Degree Graph Model.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Testing Group Properties.
Computational Complexity and Local Algorithms
Oded Goldreich, Laliv Tauber
2025 — ch.
On Testing Hamiltonicity in the Bounded Degree Graph Model.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model.
Computational Complexity and Local Algorithms
Oded Goldreich, Laliv Tauber
2025 J jnl
On doubly-sublinear interactive proofs for distributions.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Guy N. Rothblum
2025 — ch.
On the Complexity of Enumerating Ordered Sets.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On the Complexity of Estimating the Effective Support Size.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On the Cook-Mertz Tree Evaluation Procedure.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On the Locally Testable Code of Dinur et al. (2021).
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On the Lower Bound on the Length of Relaxed Locally Decodable Codes.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On the Query Complexity of Testing Local Graph Properties in the Bounded-Degree Graph Model.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
On the Relaxed LDC of BGHSV: A Survey that Corrects the Record.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
One-Sided Error Testing of Monomials and Affine Subspaces.
Computational Complexity and Local Algorithms
Oded Goldreich, Dana Ron
2025 J jnl
Proving the PCP Theorem with 1.5 proof compositions (or yet another PCP construction).
Electron. Colloquium Comput. Complex.
Oded Goldreich
2025 — ch.
Robust Self-ordering Versus Local Self-ordering.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
Solving Tree Evaluation in o(log n · log log n) Space.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
Testing Isomorphism in the Bounded-Degree Graph Model.
Computational Complexity and Local Algorithms
Oded Goldreich
2025 — ch.
Testing in the Bounded-Degree Graph Model with Degree Bound Two.
Computational Complexity and Local Algorithms
Oded Goldreich, Laliv Tauber
2024 J jnl
Doubly Sub-linear Interactive Proofs of Proximity.
Electron. Colloquium Comput. Complex.
Noga Amir, Oded Goldreich, Guy N. Rothblum
2024 J jnl
On defining PPT-search problems.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2024 J jnl
On locally-characterized expander graphs (a survey).
Electron. Colloquium Comput. Complex.
Oded Goldreich
2024 J jnl
On the Cook-Mertz Tree Evaluation procedure.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2024 J jnl
On the query complexity of testing local graph properties in the bounded-degree graph model.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2024 J jnl
On the relaxed LDC of BGHSV: A survey that corrects the record.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2024 J jnl
Solving Tree Evaluation in
Electron. Colloquium Comput. Complex.
Oded Goldreich
2023 J jnl
A Lower Bound on the Complexity of Testing Grained Distributions.
Comput. Complex.
Oded Goldreich, Dana Ron
2023 A conf
On Interactive Proofs of Proximity with Proof-Oblivious Queries.
ITCS
Oded Goldreich, Guy N. Rothblum, Tal Skverer
2023 J jnl
On Testing Group Properties.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Laliv Tauber
2023 J jnl
On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Laliv Tauber
2023 J jnl
On coarse and fine approximate counting of
Electron. Colloquium Comput. Complex.
Oded Goldreich
2023 J jnl
On teaching the approximation method for circuit lower bounds.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2023 J jnl
On the Lower Bound on the Length of Relaxed Locally Decodable Codes.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2023 J jnl
On the complexity of enumerating ordered sets.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2023 J jnl
Testing Distributions of Huge Objects.
TheoretiCS
Oded Goldreich, Dana Ron
2022 J jnl
Improved bounds on the AN-complexity of O(1)-linear functions.
Comput. Complex.
Oded Goldreich
2022 J jnl
On Interactive Proofs of Proximity with Proof-Oblivious Queries.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Guy N. Rothblum, Tal Skverer
2022 J jnl
On properties that are non-trivial to test.
Electron. Colloquium Comput. Complex.
Nader H. Bshouty, Oded Goldreich
2022 A conf
Randomness Extraction from Somewhat Dependent Sources.
ITCS
Marshall Ball, Oded Goldreich, Tal Malkin
2022 J jnl
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing.
TheoretiCS
Oded Goldreich, Avi Wigderson
2022 A conf
Testing Distributions of Huge Objects.
ITCS
Oded Goldreich, Dana Ron
2022 J jnl
Testing Distributions of Huge Objects.
CoRR
Oded Goldreich, Dana Ron
2022 J jnl
Testing in the bounded-degree graph model with degree bound two.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Laliv Tauber
2021 J jnl
A Lower Bound on the Complexity of Testing Grained Distributions.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2021 A conf
Communication Complexity with Defective Randomness.
CCC
Marshall Ball, Oded Goldreich, Tal Malkin
2021 A* conf
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model.
FOCS
Oded Goldreich, Avi Wigderson
2021 J jnl
On the Locally Testable Code of Dinur et al. (2021).
Electron. Colloquium Comput. Complex.
Oded Goldreich
2021 J jnl
Open Problems in Property Testing of Graphs.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2021 J jnl
Robust Self-Ordering versus Local Self-Ordering.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2021 A conf
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing.
CCC
Oded Goldreich, Avi Wigderson
2021 J jnl
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing.
CoRR
Oded Goldreich, Avi Wigderson
2021 J jnl
Testing Distributions of Huge Objects.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2021 J jnl
The KW Games as a Teaser.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2021 J jnl
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP.
Theor. Comput. Sci.
Oded Goldreich, Tom Gur
2020 — ch.
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy.
Computational Complexity and Property Testing
Scott E. Decatur, Oded Goldreich, Dana Ron
2020 — ch.
Bridging a Small Gap in the Gap Amplification of Assignment Testers.
Computational Complexity and Property Testing
Oded Goldreich, Or Meir
2020 J jnl
Communication Complexity with Defective Randomness.
Electron. Colloquium Comput. Complex.
Marshall Ball, Oded Goldreich, Tal Malkin
2020 — book
Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
Constant-Round Interactive Proof Systems for AC0[2] and NC1.
Computational Complexity and Property Testing
Oded Goldreich, Guy N. Rothblum
2020 J jnl
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
2020 — ch.
Deconstructing 1-Local Expanders.
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
Flexible Models for Testing Graph Properties.
Computational Complexity and Property Testing
Oded Goldreich
2020 J jnl
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
2020 — ch.
On (Valiant's) Polynomial-Size Monotone Formula for Majority.
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
Computational Complexity and Property Testing
Oded Goldreich, Avishay Tal
2020 — ch.
On Constructing Expanders for Any Number of Vertices.
Computational Complexity and Property Testing
Oded Goldreich
2020 J jnl
On Counting $t$-Cliques Mod 2.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2020 — ch.
On Emulating Interactive Proofs with Public Coins.
Computational Complexity and Property Testing
Oded Goldreich, Maya Leshkowitz
2020 J jnl
On Testing Asymmetry in the Bounded Degree Graph Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2020 J jnl
On Testing Hamiltonicity in the Bounded Degree Graph Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2020 — ch.
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing.
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
On the Effect of the Proximity Parameter on Property Testers.
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
On the Optimal Analysis of the Collision Probability Tester (an Exposition).
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition).
Computational Complexity and Property Testing
Oded Goldreich, Dana Ron
2020 — ch.
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.
Computational Complexity and Property Testing
Oded Goldreich, Avi Wigderson
2020 J jnl
One-Sided Error Testing of Monomials and Affine Subspaces.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2020 — ch.
Pseudo-mixing Time of Random Walks.
Computational Complexity and Property Testing
Itai Benjamini, Oded Goldreich
2020 — ch.
Reducing Testing Affine Spaces to Testing Linearity of Functions.
Computational Complexity and Property Testing
Oded Goldreich
2020 J jnl
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
2020 — ch.
Super-Perfect Zero-Knowledge Proofs.
Computational Complexity and Property Testing
Oded Goldreich, Liav Teichner
2020 J jnl
The Subgraph Testing Model.
ACM Trans. Comput. Theory
Oded Goldreich, Dana Ron
2020 — ch.
The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution.
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
Two Comments on Targeted Canonical Derandomizers.
Computational Complexity and Property Testing
Oded Goldreich
2020 — ch.
Worst-Case to Average-Case Reductions for Subclasses of P.
Computational Complexity and Property Testing
Oded Goldreich, Guy N. Rothblum
2019 A conf
Every Set in P Is Strongly Testable Under a Suitable Encoding.
ITCS
Irit Dinur, Oded Goldreich, Tom Gur
2019 J jnl
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity.
Comput. Complex.
Oded Goldreich
2019 — ch.
How to construct random functions.
Providing Sound Foundations for Cryptography
Oded Goldreich, Shafi Goldwasser, Silvio Micali
2019 — ch.
How to play any mental game, or a completeness theorem for protocols with honest majority.
Providing Sound Foundations for Cryptography
Oded Goldreich, Silvio Micali, Avi Wigderson
2019 J jnl
Improved bounds on the AN-complexity of multilinear functions.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2019 J jnl
Multi-pseudodeterministic algorithms.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2019 — ch.
On some noncryptographic works of Goldwasser and Micali.
Providing Sound Foundations for Cryptography
Oded Goldreich
2019 J jnl
On the Complexity of Estimating the Effective Support Size.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2019 — ch.
On the foundations of cryptography.
Providing Sound Foundations for Cryptography
Oded Goldreich
2019 — ch.
On the impact of cryptography on complexity theory.
Providing Sound Foundations for Cryptography
Oded Goldreich
2019 — ch.
Preface.
Providing Sound Foundations for Cryptography
Oded Goldreich
2019 — ch.
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design.
Providing Sound Foundations for Cryptography
Oded Goldreich, Silvio Micali, Avi Wigderson
2019 — book
Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali
Providing Sound Foundations for Cryptography
Oded Goldreich
2019 J jnl
Pseudo-Mixing Time of Random Walks.
Electron. Colloquium Comput. Complex.
Itai Benjamini, Oded Goldreich
2019 J jnl
Randomness Extraction from Somewhat Dependent Sources.
Electron. Colloquium Comput. Complex.
Marshall Ball, Oded Goldreich, Tal Malkin
2019 J jnl
Strong Locally Testable Codes with Relaxed Local Decoders.
ACM Trans. Comput. Theory
Oded Goldreich, Tom Gur, Ilan Komargodski
2019 J jnl
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model.
CoRR
Oded Goldreich
2019 J jnl
Testing Isomorphism in the Bounded-Degree Graph Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2019 A* conf
Testing graphs in vertex-distribution-free models.
STOC
Oded Goldreich
2019 A conf
The Subgraph Testing Model.
ITCS
Oded Goldreich, Dana Ron
2018 J jnl
Constant-round interactive proof systems for AC0[2] and NC1.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Guy N. Rothblum
2018 J jnl
Counting
Electron. Colloquium Comput. Complex.
Oded Goldreich, Guy N. Rothblum
2018 A* conf
Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems.
FOCS
Oded Goldreich, Guy N. Rothblum
2018 J jnl
Every set in P is strongly testable under a suitable encoding.
Electron. Colloquium Comput. Complex.
Irit Dinur, Oded Goldreich, Tom Gur
2018 J jnl
Flexible models for testing graph properties.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2018 J jnl
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2018 J jnl
Matrix rigidity of random Toeplitz matrices.
Comput. Complex.
Oded Goldreich, Avishay Tal
2018 J jnl
On Doubly-Efficient Interactive Proof Systems.
Found. Trends Theor. Comput. Sci.
Oded Goldreich
2018 J jnl
Proofs of proximity for context-free languages and read-once branching programs.
Inf. Comput.
Oded Goldreich, Tom Gur, Ron D. Rothblum
2018 A conf
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets.
ITCS
Oded Goldreich, Guy N. Rothblum
2018 J jnl
Testing Graphs in Vertex-Distribution-Free Models.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2018 J jnl
The Subgraph Testing Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2018 J jnl
Universal Locally Testable Codes.
Chic. J. Theor. Comput. Sci.
Oded Goldreich, Tom Gur
2017 — book
Introduction to Property Testing.
Oded Goldreich
2017 J jnl
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avishay Tal
2017 J jnl
On Learning and Testing Dynamic Environments.
J. ACM
Oded Goldreich, Dana Ron
2017 J jnl
On the doubly-efficient interactive proof systems of GKR.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2017 J jnl
Overview of the doubly-efficient interactive proof systems of RRR.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2017 J jnl
Simple doubly-efficient interactive proof systems for locally-characterizable sets.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Guy N. Rothblum
2017 J jnl
Worst-case to Average-case reductions for subclasses of P.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Guy N. Rothblum
2016 J jnl
Deconstructing 1-local expanders.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2016 — ch.
Estimating Simple Graph Parameters in Sublinear Time.
Encyclopedia of Algorithms
Oded Goldreich, Dana Ron
2016 A* conf
Matrix rigidity of random toeplitz matrices.
STOC
Oded Goldreich, Avishay Tal
2016 J jnl
On Emulating Interactive Proofs with Public Coins.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Maya Leshkowitz
2016 J jnl
On Sample-Based Testers.
ACM Trans. Comput. Theory
Oded Goldreich, Dana Ron
2016 J jnl
Reducing testing affine spaces to testing linearity.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2016 J jnl
Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword.
Comput. Complex.
Oded Goldreich
2016 — ch.
Testing Bipartiteness in the Dense-Graph Model.
Encyclopedia of Algorithms
Oded Goldreich, Dana Ron
2016 — ch.
Testing Bipartiteness of Graphs in Sublinear Time.
Encyclopedia of Algorithms
Oded Goldreich, Dana Ron
2016 J jnl
The uniform distribution is complete with respect to testing identity to a fixed distribution.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2016 J jnl
Two-sided error proximity oblivious testing.
Random Struct. Algorithms
Oded Goldreich, Igor Shinkar
2016 J jnl
Universal Locally Testable Codes.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur
2016 J jnl
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur
2015 J jnl
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
ACM Trans. Comput. Theory
Oded Goldreich, Or Meir
2015 J jnl
Matrix Rigidity of Random Toeplitz Matrices.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avishay Tal
2015 A conf
On Randomness Extraction in AC0.
CCC
Oded Goldreich, Emanuele Viola, Avi Wigderson
2015 J jnl
On Randomness Extraction in AC0.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Emanuele Viola, Avi Wigderson
2015 A conf
On Sample-Based Testers.
ITCS
Oded Goldreich, Dana Ron
2015 — conf
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract).
ICALP (1)
Oded Goldreich, Tom Gur, Ron D. Rothblum
2015 J jnl
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur, Ron Rothblum
2015 A conf
Strong Locally Testable Codes with Relaxed Local Decoders.
CCC
Oded Goldreich, Tom Gur, Ilan Komargodski
2014 J jnl
Finding cycles and trees in sublinear time.
Random Struct. Algorithms
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2014 A* conf
On Learning and Testing Dynamic Environments.
FOCS
Oded Goldreich, Dana Ron
2014 J jnl
On Learning and Testing Dynamic Environments.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2014 — conf
On Multiple Input Problems in Property Testing.
APPROX-RANDOM
Oded Goldreich
2014 A* conf
On derandomizing algorithms that err extremely rarely.
STOC
Oded Goldreich, Avi Wigderson
2014 J jnl
Strong Locally Testable Codes with Relaxed Local Decoders.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur, Ilan Komargodski
2014 J jnl
Super-Perfect Zero-Knowledge Proofs.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Liav Teichner
2013 — ch.
A Short Tutorial of Zero-Knowledge.
Secure Multi-Party Computation
Oded Goldreich
2013 J jnl
Enhancements of Trapdoor Permutations.
J. Cryptol.
Oded Goldreich, Ron D. Rothblum
2013 — ch.
General Cryptographic Protocols: The Very Basics.
Secure Multi-Party Computation
Oded Goldreich
2013 J jnl
More Constructions of Lossy and Correlation-Secure Trapdoor Functions.
J. Cryptol.
David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, Gil Segev
2013 J jnl
On Derandomizing Algorithms that Err Extremely Rarely.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
2013 J jnl
On Multiple Input Problems in Property Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2013 J jnl
On Sample-Based Testers.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2013 J jnl
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2013 J jnl
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
2013 A conf
On the possibilities and limitations of pseudodeterministic algorithms.
ITCS
Oded Goldreich, Shafi Goldwasser, Dana Ron
2012 J jnl
A theory of goal-oriented communication.
J. ACM
Oded Goldreich, Brendan Juba, Madhu Sudan
2012 J jnl
Finding Cycles and Trees in Sublinear Time.
Electron. Colloquium Comput. Complex.
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2012 J jnl
Hierarchy Theorems for Property Testing.
Comput. Complex.
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2012 J jnl
Invitation to complexity theory.
XRDS
Oded Goldreich
2012 J jnl
Monotone Circuits: One-Way Functions versus Pseudorandom Generators.
Theory Comput.
Oded Goldreich, Rani Izsak
2012 J jnl
On intellectual and instrumental values in science.
SIGACT News
Oded Goldreich
2012 J jnl
On struggle and competition in scientic fields.
SIGACT News
Oded Goldreich
2012 J jnl
On the (im)possibility of obfuscating programs.
J. ACM
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2012 J jnl
On the Effect of the Proximity Parameter on Property Testers.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2012 J jnl
On the possibilities and limitations of pseudodeterministic algorithms.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Dana Ron
2012 J jnl
Special issue from RANDOM'09: Editors' Foreword.
Comput. Complex.
Oded Goldreich, Salil P. Vadhan
2012 J jnl
The tensor product of two good codes is not necessarily robustly testable.
Inf. Process. Lett.
Oded Goldreich, Or Meir
2012 — conf
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract).
APPROX-RANDOM
Oded Goldreich, Igor Shinkar
2012 J jnl
Two-Sided Error Proximity Oblivious Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2011 — ch.
A Brief Introduction to Property Testing.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
A Candidate Counterexample to the Easy Cylinders Conjecture.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
A Sample of Samplers: A Computational Perspective on Sampling.
Studies in Complexity and Cryptography
Oded Goldreich
2011 A* conf
A theory of goal-oriented communication.
PODC
Oded Goldreich, Brendan Juba, Madhu Sudan
2011 J jnl
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
SIAM J. Comput.
Oded Goldreich, Dana Ron
2011 — ch.
Another Motivation for Reducing the Randomness Complexity of Algorithms.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Another Proof That
Studies in Complexity and Cryptography
Oded Goldreich, David Zuckerman
2011 — ch.
Average Case Complexity, Revisited.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Basic Facts about Expander Graphs.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Bravely, Moderately: A Common Theme in Four Recent Works.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Candidate One-Way Functions Based on Expander Graphs.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Collision-Free Hashing from Lattice Problems.
Studies in Complexity and Cryptography
Oded Goldreich, Shafi Goldwasser, Shai Halevi
2011 — ch.
Contemplations on Testing Graph Properties.
Studies in Complexity and Cryptography
Oded Goldreich
2011 J jnl
Enhancements of Trapdoor Permutations.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Ron Rothblum
2011 — ch.
Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
From Absolute Distinguishability to Positive Distinguishability.
Studies in Complexity and Cryptography
Zvika Brakerski, Oded Goldreich
2011 — ch.
From Logarithmic Advice to Single-Bit Advice.
Studies in Complexity and Cryptography
Oded Goldreich, Madhu Sudan, Luca Trevisan
2011 — ch.
In a World of P=BPP.
Studies in Complexity and Cryptography
Oded Goldreich
2011 J jnl
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Or Meir
2011 — ch.
Introduction to Testing Graph Properties.
Studies in Complexity and Cryptography
Oded Goldreich
2011 J jnl
Monotone Circuits: One-Way Functions versus Pseudorandom Generators.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Rani Izsak
2011 — ch.
Notes on Levin's Theory of Average-Case Complexity.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
On Constructing 1-1 One-Way Functions.
Studies in Complexity and Cryptography
Oded Goldreich, Leonid A. Levin, Noam Nisan
2011 — ch.
On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge.
Studies in Complexity and Cryptography
Mihir Bellare, Oded Goldreich
2011 J jnl
On Proximity-Oblivious Testing.
SIAM J. Comput.
Oded Goldreich, Dana Ron
2011 — ch.
On Security Preserving Reductions - Revised Terminology.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
On Testing Expansion in Bounded-Degree Graphs.
Studies in Complexity and Cryptography
Oded Goldreich, Dana Ron
2011 — ch.
On Yao's XOR-Lemma.
Studies in Complexity and Cryptography
Oded Goldreich, Noam Nisan, Avi Wigderson
2011 — ch.
On the Average-Case Complexity of Property Testing.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
On the Circuit Complexity of Perfect Hashing.
Studies in Complexity and Cryptography
Oded Goldreich, Avi Wigderson
2011 — ch.
On the Complexity of Computational Problems Regarding Distributions.
Studies in Complexity and Cryptography
Oded Goldreich, Salil P. Vadhan
2011 J jnl
On the complexity of computational problems regarding distributions (a survey).
Electron. Colloquium Comput. Complex.
Oded Goldreich, Salil P. Vadhan
2011 — ch.
Proving Computational Ability.
Studies in Complexity and Cryptography
Mihir Bellare, Oded Goldreich
2011 — ch.
Proximity Oblivious Testing and the Role of Invariances.
Studies in Complexity and Cryptography
Oded Goldreich, Tali Kaufman
2011 — conf
Proximity Oblivious Testing and the Role of Invariances.
APPROX-RANDOM
Oded Goldreich, Tali Kaufman
2011 — ch.
Randomness and Computation.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Short Locally Testable Codes and Proofs.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Simplified Derandomization of BPP Using a Hitting Set Generator.
Studies in Complexity and Cryptography
Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2011 — ch.
Strong Proofs of Knowledge.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — book
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Testing Graph Blow-Up.
Studies in Complexity and Cryptography
Lidor Avigad, Oded Goldreich
2011 — conf
Testing Graph Blow-Up.
APPROX-RANDOM
Lidor Avigad, Oded Goldreich
2011 — ch.
The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles.
Studies in Complexity and Cryptography
Oded Goldreich
2011 — ch.
Three XOR-Lemmas - An Exposition.
Studies in Complexity and Cryptography
Oded Goldreich
2011 J jnl
Two Comments on Targeted Canonical Derandomizers.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2011 — ch.
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.
Studies in Complexity and Cryptography
Oded Goldreich
2010 — ch.
A Brief Introduction to Property Testing.
Property Testing
Oded Goldreich
2010 — ch.
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Property Testing
Oded Goldreich, Dana Ron
2010 A* conf
Erratum for: on basing one-way functions on NP-hardness.
STOC
Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz
2010 J jnl
Finding Cycles and Trees in Sublinear Time
CoRR
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2010 — ch.
Hierarchy Theorems for Property Testing.
Property Testing
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2010 J jnl
In a World of P=BPP.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2010 — ch.
Introduction to Testing Graph Properties.
Property Testing
Oded Goldreich
2010 J jnl
Introduction to Testing Graph Properties.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2010 — conf
More Constructions of Lossy and Correlation-Secure Trapdoor Functions.
Public Key Cryptography
David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, Gil Segev
2010 J jnl
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.
J. Cryptol.
Oded Goldreich
2010 — conf
On Testing Computability by Small Width OBDDs.
APPROX-RANDOM
Oded Goldreich
2010 J jnl
On Testing Computability by Small Width OBDDs.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2010 J jnl
On The Randomness Complexity of Property Testing.
Comput. Complex.
Oded Goldreich, Or Sheffet
2010 J jnl
On the Implementation of Huge Random Objects.
SIAM J. Comput.
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
2010 — book
P, NP, and NP-Completeness: The Basics of Complexity Theory.
Oded Goldreich
2010 — book
Property Testing - Current Research and Surveys
Property Testing
Oded Goldreich
2010 J jnl
Proximity Oblivious Testing and the Role of Invariances.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tali Kaufman
2010 — ch.
Short Locally Testable Codes and Proofs: A Survey in Two Parts.
Property Testing
Oded Goldreich
2010 — ch.
The Program of the Mini-Workshop.
Property Testing
Oded Goldreich
2009 J jnl
A Candidate Counterexample to the Easy Cylinders Conjecture.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2009 J jnl
A Theory of Goal-Oriented Communication.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Brendan Juba, Madhu Sudan
2009 — conf
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
APPROX-RANDOM
Oded Goldreich, Dana Ron
2009 J jnl
From absolute distinguishability to positive distinguishability.
Electron. Colloquium Comput. Complex.
Zvika Brakerski, Oded Goldreich
2009 — conf
Hierarchy Theorems for Property Testing.
APPROX-RANDOM
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2009 J jnl
More Constructions of Lossy and Correlation-Secure Trapdoor Functions.
IACR Cryptol. ePrint Arch.
David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, Gil Segev
2009 J jnl
On our duties as scientists.
SIGACT News
Oded Goldreich
2009 A* conf
On proximity oblivious testing.
STOC
Oded Goldreich, Dana Ron
2008 J jnl
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2008 J jnl
Approximating average parameters of graphs.
Random Struct. Algorithms
Oded Goldreich, Dana Ron
2008 — book
Computational complexity - a conceptual perspective.
Oded Goldreich
2008 J jnl
Computational complexity: a conceptual perspective.
SIGACT News
Oded Goldreich
2008 J jnl
Hierarchy Theorems for Property Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg
2008 J jnl
On Proximity Oblivious Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2008 J jnl
Preface to the Special Issue from Random'06.
Comput. Complex.
Oded Goldreich
2008 J jnl
Probabilistic Proof Systems: A Primer.
Found. Trends Theor. Comput. Sci.
Oded Goldreich
2008 J jnl
Universal Arguments and their Applications.
SIAM J. Comput.
Boaz Barak, Oded Goldreich
2007 — conf
On Approximating the Average Distance Between Points.
APPROX-RANDOM
Kfir Barhum, Oded Goldreich, Adi Shraibman
2007 B conf
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.
TCC
Oded Goldreich
2007 J jnl
On the Average-Case Complexity of Property Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2007 — conf
On the Randomness Complexity of Property Testing.
APPROX-RANDOM
Oded Goldreich, Or Sheffet
2007 J jnl
On the randomness complexity of property testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Or Sheffet
2007 J jnl
Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword.
Comput. Complex.
Oded Goldreich, Salil P. Vadhan
2007 J jnl
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Or Meir
2006 — conf
Approximating Average Parameters of Graphs.
APPROX-RANDOM
Oded Goldreich, Dana Ron
2006 — conf
Concurrent Zero-Knowledge with Timing, Revisited.
Essays in Memory of Shimon Even
Oded Goldreich
2006 J jnl
Locally testable codes and PCPs of almost-linear length.
J. ACM
Oded Goldreich, Madhu Sudan
2006 J jnl
Lower bounds for linear locally decodable codes and private information retrieval.
Comput. Complex.
Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
2006 J jnl
On Expected Probabilistic Polynomial-Time Adversaries - A suggestion for restricted definitions and their benefits.
IACR Cryptol. ePrint Arch.
Oded Goldreich
2006 J jnl
On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2006 J jnl
On Post-Modern Cryptography.
IACR Cryptol. ePrint Arch.
Oded Goldreich
2006 J jnl
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
Electron. Colloquium Comput. Complex.
Mihir Bellare, Oded Goldreich
2006 J jnl
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
IACR Cryptol. ePrint Arch.
Mihir Bellare, Oded Goldreich
2006 — conf
On Promise Problems: A Survey.
Essays in Memory of Shimon Even
Oded Goldreich
2006 — conf
On Teaching the Basics of Complexity Theory.
Essays in Memory of Shimon Even
Oded Goldreich
2006 A* conf
On basing one-way functions on NP-hardness.
STOC
Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz
2006 J jnl
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.
SIAM J. Comput.
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2006 J jnl
Session-Key Generation Using Human Passwords Only.
J. Cryptol.
Oded Goldreich, Yehuda Lindell
2006 J jnl
Special Issue on Randomness and Complexity.
SIAM J. Comput.
Oded Goldreich, Madhu Sudan
2006 — ed.
Theoretical Computer Science, Essays in Memory of Shimon Even
Essays in Memory of Shimon Even
Oded Goldreich, Arnold L. Rosenberg, Alan L. Selman
2005 — conf
Approximating Average Parameters of Graphs.
Sublinear Algorithms
Oded Goldreich, Dana Ron
2005 J jnl
Approximating Average Parameters of Graphs.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2005 J jnl
Bravely, Moderately: A Common Theme in Four Recent Results
Electron. Colloquium Comput. Complex.
Oded Goldreich
2005 — conf
Contemplations on Testing Graph Properties.
Sublinear Algorithms
Oded Goldreich
2005 J jnl
Foundations of Cryptography - A Primer.
Found. Trends Theor. Comput. Sci.
Oded Goldreich
2005 J jnl
On Promise Problems (a survey in memory of Shimon Even [1935-2004])
Electron. Colloquium Comput. Complex.
Oded Goldreich
2005 J jnl
Short Locally Testable Codes and Proofs (Survey)
Electron. Colloquium Comput. Complex.
Oded Goldreich
2005 A conf
Short PCPs Verifiable in Polylogarithmic Time.
CCC
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2004 J jnl
From logarithmic advice to single-bit advice
Electron. Colloquium Comput. Complex.
Oded Goldreich, Madhu Sudan, Luca Trevisan
2004 J jnl
On Estimating the Average Degree of a Graph
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2004 B conf
On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes.
TCC
Ran Canetti, Oded Goldreich, Shai Halevi
2004 — ch.
Preface to "Week Three: Randomness in Computation".
Computational Complexity Theory
Oded Goldreich
2004 J jnl
Preface.
J. Cryptol.
Oded Goldreich
2004 — ch.
Pseudorandomness - Part I.
Computational Complexity Theory
Oded Goldreich
2004 J jnl
Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2004 A* conf
Robust pcps of proximity, shorter pcps and applications to coding.
STOC
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2004 — book
The Foundations of Cryptography - Volume 2: Basic Applications.
Oded Goldreich
2004 J jnl
The Power of Verification Queries in Message Authentication and Authenticated Encryption.
IACR Cryptol. ePrint Arch.
Mihir Bellare, Oded Goldreich, Anton Mityagin
2004 J jnl
The random oracle methodology, revisited.
J. ACM
Ran Canetti, Oded Goldreich, Shai Halevi
2003 J jnl
Almost k-wise independence versus k-wise independence.
Inf. Process. Lett.
Noga Alon, Oded Goldreich, Yishay Mansour
2003 — conf
Bounds on 2-Query Codeword Testing.
RANDOM-APPROX
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
2003 J jnl
Bounds on 2-Query Codeword Testing.
Electron. Colloquium Comput. Complex.
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
2003 J jnl
Cryptography and cryptographic protocols.
Distributed Comput.
Oded Goldreich
2003 A* conf
On the Implementation of Huge Random Objects.
FOCS
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
2003 J jnl
On the Implementation of Huge Random Objects.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Asaf Nussboim
2003 J jnl
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators.
J. Cryptol.
Oded Goldreich, Vered Rosen
2003 J jnl
On the random-oracle methodology as applied to length-restricted signature schemes.
IACR Cryptol. ePrint Arch.
Ran Canetti, Oded Goldreich, Shai Halevi
2003 J jnl
Three theorems regarding testing graph properties.
Random Struct. Algorithms
Oded Goldreich, Luca Trevisan
2002 J jnl
Almost k-wise independence versus k-wise independence.
Electron. Colloquium Comput. Complex.
Noga Alon, Oded Goldreich, Yishay Mansour
2002 A* conf
Concurrent zero-knowledge with timing, revisited.
STOC
Oded Goldreich
2002 — conf
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good.
RANDOM
Oded Goldreich, Avi Wigderson
2002 J jnl
Derandomization that is rarely wrong from short advice that is typically good
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
2002 J jnl
Locally Testable Codes and PCPs of Almost-Linear Length
Electron. Colloquium Comput. Complex.
Oded Goldreich, Madhu Sudan
2002 A* conf
Locally Testable Codes and PCPs of Almost-Linear Length.
FOCS
Oded Goldreich, Madhu Sudan
2002 A conf
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval.
CCC
Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
2002 J jnl
On Chosen Ciphertext Security of Multiple Encryptions.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Yoad Lustig, Moni Naor
2002 J jnl
On interactive proofs with a laconic prover.
Comput. Complex.
Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2002 J jnl
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators
Electron. Colloquium Comput. Complex.
Oded Goldreich, Vered Rosen
2002 J jnl
Property Testing in Bounded Degree Graphs.
Algorithmica
Oded Goldreich, Dana Ron
2002 J jnl
The GGM Construction does NOT yield Correlation Intractable Function Ensembles.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2002 J jnl
The GGM Construction does NOT yield Correlation Intractable Function Ensembles.
IACR Cryptol. ePrint Arch.
Oded Goldreich
2002 A conf
Universal Arguments and their Applications.
CCC
Boaz Barak, Oded Goldreich
2002 J jnl
Zero-Knowledge twenty years after its invention
Electron. Colloquium Comput. Complex.
Oded Goldreich
2002 J jnl
Zero-Knowledge twenty years after its invention.
IACR Cryptol. ePrint Arch.
Oded Goldreich
2002 A* conf
Zero-Knowledge.
FOCS
Oded Goldreich
2001 J jnl
Concurrent Zero-Knowledge With Timing, Revisited
Electron. Colloquium Comput. Complex.
Oded Goldreich
2001 J jnl
Concurrent Zero-Knowledge With Timing, Revisited.
IACR Cryptol. ePrint Arch.
Oded Goldreich
2001 J jnl
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
Electron. Colloquium Comput. Complex.
Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
2001 J jnl
On Interactive Proofs with a Laconic Prover
Electron. Colloquium Comput. Complex.
Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2001 A* conf
On Interactive Proofs with a Laconic Prover.
ICALP
Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2001 J jnl
On the (Im)possibility of Obfuscating Programs
Electron. Colloquium Comput. Complex.
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2001 A* conf
On the (Im)possibility of Obfuscating Programs.
CRYPTO
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2001 J jnl
On the (Im)possibility of Obfuscating Programs.
IACR Cryptol. ePrint Arch.
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang
2001 A* conf
Resettably-Sound Zero-Knowledge and its Applications.
FOCS
Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell
2001 J jnl
Resettably-Sound Zero-Knowledge and its Applications.
IACR Cryptol. ePrint Arch.
Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell
2001 A* conf
Session-Key Generation Using Human Passwords Only.
CRYPTO
Oded Goldreich, Yehuda Lindell
2001 — book
The Foundations of Cryptography - Volume 1: Basic Techniques.
Oded Goldreich
2001 A* conf
Three Theorems Regarding Testing Graph Properties.
FOCS
Oded Goldreich, Luca Trevisan
2001 J jnl
Three Theorems regarding Testing Graph Properties.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Luca Trevisan
2001 J jnl
Universal Arguments and their Applications.
Electron. Colloquium Comput. Complex.
Boaz Barak, Oded Goldreich
2001 J jnl
Universal Arguments and their Applications.
IACR Cryptol. ePrint Arch.
Boaz Barak, Oded Goldreich
2001 J jnl
Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.
Electron. Colloquium Comput. Complex.
Oded Goldreich
2000 J jnl
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
SIAM J. Comput.
Oded Goldreich, Shmuel Safra
2000 J jnl
Candidate One-Way Functions Based on Expander Graphs
Electron. Colloquium Comput. Complex.
Oded Goldreich
2000 J jnl
Candidate One-Way Functions Based on Expander Graphs.
IACR Cryptol. ePrint Arch.
Oded Goldreich
2000 J jnl
Chinese remaindering with errors.
IEEE Trans. Inf. Theory
Oded Goldreich, Dana Ron, Madhu Sudan
2000 J jnl
Learning Polynomials with Queries: The Highly Noisy Case.
SIAM J. Discret. Math.
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
2000 J jnl
On Pseudorandomness with respect to Deterministic Observers.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
2000 — conf
On Pseudorandomness with respect to Deterministic Observes.
ICALP Satellite Workshops
Oded Goldreich, Avi Wigderson
2000 J jnl
On Security Preserving Reductions - Revised Terminology.
IACR Cryptol. ePrint Arch.
Oded Goldreich
2000 J jnl
On Testing Expansion in Bounded-Degree Graphs
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2000 J jnl
On the Limits of Nonapproximability of Lattice Problems.
J. Comput. Syst. Sci.
Oded Goldreich, Shafi Goldwasser
2000 J jnl
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Vered Rosen
2000 J jnl
Preface.
J. Cryptol.
Oded Goldreich
2000 A* conf
Pseudorandomness.
ICALP
Oded Goldreich
2000 A* conf
Resettable zero-knowledge (extended abstract).
STOC
Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
2000 J jnl
Session-Key Generation using Human Passwords Only.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Yehuda Lindell
2000 J jnl
Simplified derandomization of BPP using a hitting set generator.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Salil P. Vadhan, Avi Wigderson
2000 J jnl
Testing Monotonicity.
Comb.
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky
2000 J jnl
The Random Oracle Methodology, Revisited
CoRR
Ran Canetti, Oded Goldreich, Shai Halevi
2000 J jnl
Uniform Generation of NP-Witnesses Using an NP-Oracle.
Inf. Comput.
Mihir Bellare, Oded Goldreich, Erez Petrank
1999 J jnl
A Sublinear Bipartiteness Tester for Bounded Degree Graphs.
Comb.
Oded Goldreich, Dana Ron
1999 J jnl
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
1999 J jnl
Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.
Inf. Process. Lett.
Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
1999 A* conf
Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK.
CRYPTO
Oded Goldreich, Amit Sahai, Salil P. Vadhan
1999 J jnl
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK
Electron. Colloquium Comput. Complex.
Oded Goldreich, Amit Sahai, Salil P. Vadhan
1999 A* conf
Chinese Remaindering with Errors.
STOC
Oded Goldreich, Dana Ron, Madhu Sudan
1999 J jnl
Chinese Remaindering with Errors.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Dana Ron, Madhu Sudan
1999 A conf
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK.
CCC
Oded Goldreich, Salil P. Vadhan
1999 J jnl
Computational Indistinguishability: A Sample Hierarchy.
J. Comput. Syst. Sci.
Oded Goldreich, Madhu Sudan
1999 J jnl
Computational Sample Complexity.
SIAM J. Comput.
Scott E. Decatur, Oded Goldreich, Dana Ron
1999 A conf
Deterministic Amplification of Space-Bounded Probabilistic Algorithms.
CCC
Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson
1999 — conf
Improved Derandomization of BPP Using a Hitting Set Generator.
RANDOM-APPROX
Oded Goldreich, Avi Wigderson
1999 — conf
Improved Testing Algorithms for Monotonicity.
RANDOM-APPROX
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
1999 J jnl
Improved Testing Algorithms for Monotonicity.
Electron. Colloquium Comput. Complex.
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
1999 J jnl
Interleaved Zero-Knowledge in the Public-Key Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Silvio Micali
1999 J jnl
Interleaved Zero-Knowledge in the Public-Key Model.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Shafi Goldwasser, Silvio Micali
1999 J jnl
Quantifying Knowledge Complexity.
Comput. Complex.
Oded Goldreich, Erez Petrank
1999 J jnl
Resettable Zero-Knowledge.
Electron. Colloquium Comput. Complex.
Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
1999 J jnl
Resettable Zero-Knowledge.
IACR Cryptol. ePrint Arch.
Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali
1999 A* conf
Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier.
CRYPTO
Mihir Bellare, Oded Goldreich, Hugo Krawczyk
1999 J jnl
The Graph Clustering Problem has a Perfect Zero-Knowledge Interactive Proof.
Inf. Process. Lett.
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano
1998 A* conf
A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
STOC
Oded Goldreich, Dana Ron
1998 J jnl
Chinese Remaindering with Errors
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron, Madhu Sudan
1998 J jnl
Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK
Electron. Colloquium Comput. Complex.
Oded Goldreich, Salil P. Vadhan
1998 J jnl
Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Salil P. Vadhan
1998 J jnl
Computational Complexity and Knowledge Complexity.
SIAM J. Comput.
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
1998 J jnl
Computational Indistinguishability: A Sample Hierarchy
Electron. Colloquium Comput. Complex.
Oded Goldreich, Madhu Sudan
1998 A conf
Computational Indistinguishability: A Sample Hierarchy.
CCC
Oded Goldreich, Madhu Sudan
1998 J jnl
Computational Indistinguishability: Algorithms vs. Circuits.
Theor. Comput. Sci.
Oded Goldreich, Bernd Meyer
1998 J jnl
Deterministic Amplification of Space Bounded Probabilistic Algorithms.
Electron. Colloquium Comput. Complex.
Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson
1998 J jnl
Efficient approximation of product distributions.
Random Struct. Algorithms
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
1998 J jnl
Fault-Tolerant Computation in the Full Information Model.
SIAM J. Comput.
Oded Goldreich, Shafi Goldwasser, Nathan Linial
1998 J jnl
Free Bits, PCPs, and Nonapproximability-Towards Tight Results.
SIAM J. Comput.
Mihir Bellare, Oded Goldreich, Madhu Sudan
1998 A* conf
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
STOC
Oded Goldreich, Amit Sahai, Salil P. Vadhan
1998 J jnl
Learning Polynomials with Queries - The Highly Noisy Case.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
1998 — book
Modern Cryptography, Probabilistic Proofs and Pseudorandomness.
Oded Goldreich
1998 J jnl
On the Complexity of Interactive Proofs with Bounded Communication.
Inf. Process. Lett.
Oded Goldreich, Johan Håstad
1998 A* conf
On the Limits of Non-Approximability of Lattice Problems.
STOC
Oded Goldreich, Shafi Goldwasser
1998 J jnl
On the possibility of basing Cryptography on the assumption that P ≠ NP.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Shafi Goldwasser
1998 J jnl
Private Information Retrieval.
J. ACM
Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan
1998 J jnl
Property Testing and its Connection to Learning and Approximation.
J. ACM
Oded Goldreich, Shafi Goldwasser, Dana Ron
1998 A* conf
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop.
CRYPTO
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
1998 A* conf
Testing Monotonicity.
FOCS
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron
1998 J jnl
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
Electron. Colloquium Comput. Complex.
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano
1998 J jnl
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.
IACR Cryptol. ePrint Arch.
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano
1998 A* conf
The Random Oracle Methodology, Revisited (Preliminary Version).
STOC
Ran Canetti, Oded Goldreich, Shai Halevi
1998 J jnl
The Random Oracle Methodology, Revisited.
IACR Cryptol. ePrint Arch.
Ran Canetti, Oded Goldreich, Shai Halevi
1998 J jnl
Uniform Generation of NP-witnesses using an NP-oracle.
Electron. Colloquium Comput. Complex.
Mihir Bellare, Oded Goldreich, Erez Petrank
1997 — conf
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
RANDOM
Oded Goldreich, Shmuel Safra
1997 J jnl
A Probabilistic Error-Correcting Scheme.
IACR Cryptol. ePrint Arch.
Scott E. Decatur, Oded Goldreich, Dana Ron
1997 J jnl
A Sample of Samplers - A Computational Perspective on Sampling (survey).
Electron. Colloquium Comput. Complex.
Oded Goldreich
1997 J jnl
Another proof that BPP subseteq PH (and more).
Electron. Colloquium Comput. Complex.
Oded Goldreich, David Zuckerman
1997 J jnl
Combinatorial Property Testing (a survey).
Electron. Colloquium Comput. Complex.
Oded Goldreich
1997 — conf
Combinatorial property testing (a survey).
Randomization Methods in Algorithm Design
Oded Goldreich
1997 J jnl
Computational Sample Complexity
Electron. Colloquium Comput. Complex.
Scott E. Decatur, Oded Goldreich, Dana Ron
1997 A* conf
Computational Sample Complexity.
COLT
Scott E. Decatur, Oded Goldreich, Dana Ron
1997 A* conf
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.
CRYPTO
Oded Goldreich, Shafi Goldwasser, Shai Halevi
1997 J jnl
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Shai Halevi
1997 J jnl
Notes on Levin's Theory of Average-Case Complexity.
Electron. Colloquium Comput. Complex.
Oded Goldreich
1997 J jnl
On Universal Learning Algorithms.
Inf. Process. Lett.
Oded Goldreich, Dana Ron
1997 A* conf
On the Foundations of Modern Cryptography.
CRYPTO
Oded Goldreich
1997 J jnl
On the Limits of Non-Approximability of Lattice Problems
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser
1997 A conf
Probabilistic Proof Systems - A Survey.
STACS
Oded Goldreich
1997 A* conf
Property Testing in Bounded Degree Graphs.
STOC
Oded Goldreich, Dana Ron
1997 A* conf
Public-Key Cryptosystems from Lattice Reduction Problems.
CRYPTO
Oded Goldreich, Shafi Goldwasser, Shai Halevi
1997 J jnl
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
1997 J jnl
Theory of computing: a scientific perspective (extended abstract).
SIGACT News
Oded Goldreich, Avi Wigderson
1997 J jnl
Tiny families of functions with random properties: A quality-size trade-off for hashing.
Random Struct. Algorithms
Oded Goldreich, Avi Wigderson
1996 J jnl
A Combinatorial Consistency Lemma with application to the PCP Theorem
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shmuel Safra
1996 A* conf
Adaptively Secure Multi-Party Computation.
STOC
Ran Canetti, Uriel Feige, Oded Goldreich, Moni Naor
1996 J jnl
Collision-Free Hashing from Lattice Problems
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Shai Halevi
1996 J jnl
Collision-Free Hashing from Lattice Problems.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Shafi Goldwasser, Shai Halevi
1996 J jnl
Computational Indistinguishability - Algorithms vs. Circuits.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Bernd Meyer
1996 J jnl
How to Construct Constant-Round Zero-Knowledge Proof Systems for NP.
J. Cryptol.
Oded Goldreich, Ariel Kahan
1996 J jnl
On the Circuit Complexity of Perfect Hashing
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
1996 J jnl
On the Composition of Zero-Knowledge Proof Systems.
SIAM J. Comput.
Oded Goldreich, Hugo Krawczyk
1996 J jnl
On the Message Complexity of Interactive Proof Systems
Electron. Colloquium Comput. Complex.
Oded Goldreich, Johan Håstad
1996 J jnl
On-Line/Off-Line Digital Signatures.
J. Cryptol.
Shimon Even, Oded Goldreich, Silvio Micali
1996 A* conf
Property Testing and Its Connection to Learning and Approximation.
FOCS
Oded Goldreich, Shafi Goldwasser, Dana Ron
1996 J jnl
Property Testing and its connection to Learning and Approximation
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Dana Ron
1996 J jnl
Public-Key Cryptosystems from Lattice Reduction Problems
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Shai Halevi
1996 J jnl
Public-Key Cryptosystems from Lattice Reduction Problems.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Shafi Goldwasser, Shai Halevi
1996 J jnl
Software Protection and Simulation on Oblivious RAMs.
J. ACM
Oded Goldreich, Rafail Ostrovsky
1996 J jnl
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.
Electron. Colloquium Comput. Complex.
Oded Goldreich
1996 J jnl
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof.
IACR Cryptol. ePrint Arch.
Oded Goldreich
1996 J jnl
The future of computational complexity theory: part I.
SIGACT News
Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser
1996 J jnl
Theory of Computing: A Scientific Perspective.
ACM Comput. Surv.
Oded Goldreich, Avi Wigderson
1995 J jnl
Free Bits, PCP and Non-Approximability - Towards Tight Results
Electron. Colloquium Comput. Complex.
Mihir Bellare, Oded Goldreich, Madhu Sudan
1995 A* conf
Free Bits, PCPs and Non-Approximability - Towards Tight Results.
FOCS
Mihir Bellare, Oded Goldreich, Madhu Sudan
1995 A* conf
Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs.
CRYPTO
Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson
1995 A* conf
Incremental cryptography and application to virus protection.
STOC
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
1995 A* conf
Learning Polynomials with Queries: The Highly Noisy Case.
FOCS
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
1995 J jnl
Lower Bounds for Sampling Algorithms for Estimating the Average.
Inf. Process. Lett.
Ran Canetti, Guy Even, Oded Goldreich
1995 J jnl
On Constructing 1-1 One-Way Functions
Electron. Colloquium Comput. Complex.
Oded Goldreich, Leonid A. Levin, Noam Nisan
1995 J jnl
On Yao's XOR-Lemma
Electron. Colloquium Comput. Complex.
Oded Goldreich, Noam Nisan, Avi Wigderson
1995 A* conf
Private Information Retrieval.
FOCS
Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan
1995 J jnl
Three XOR-Lemmas - An Exposition
Electron. Colloquium Comput. Complex.
Oded Goldreich
1994 J jnl
A taxonomy of proof systems (part 2).
SIGACT News
Oded Goldreich
1994 J jnl
Computational Complexity and Knowledge Complexity
Electron. Colloquium Comput. Complex.
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
1994 A* conf
Computational complexity and knowledge complexity (extended abstract).
STOC
Oded Goldreich, Rafail Ostrovsky, Erez Petrank
1994 J jnl
Definitions and Properties of Zero-Knowledge Proof Systems.
J. Cryptol.
Oded Goldreich, Yair Oren
1994 A* conf
Incremental Cryptography: The Case of Hashing and Signing.
CRYPTO
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
1994 J jnl
Probabilistic Proof Systems (A Survey)
Electron. Colloquium Comput. Complex.
Oded Goldreich
1994 J jnl
The Random Oracle Hypothesis Is False.
J. Comput. Syst. Sci.
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi
1994 J jnl
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing
Electron. Colloquium Comput. Complex.
Oded Goldreich, Avi Wigderson
1994 A* conf
Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing.
STOC
Oded Goldreich, Avi Wigderson
1993 J jnl
A Perfect Zero-Knowledge Proof System for a Problem Equivalent to the Discrete Logarithm.
J. Cryptol.
Oded Goldreich, Eyal Kushilevitz
1993 J jnl
A Uniform-Complexity Treatment of Encryption and Zero-Knowledge.
J. Cryptol.
Oded Goldreich
1993 J jnl
A taxonomy of proof systems (part 1).
SIGACT News
Oded Goldreich
1993 J jnl
Addendum to "Simple Construction of Almost k-wise Independent Random Variables".
Random Struct. Algorithms
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
1993 A* conf
Asynchronous secure computation.
STOC
Michael Ben-Or, Ran Canetti, Oded Goldreich
1993 J jnl
Bounds on Tradeoffs Between Randomness and Communication Complexity.
Comput. Complex.
Ran Canetti, Oded Goldreich
1993 J jnl
On the Existence of Pseudorandom Generators.
SIAM J. Comput.
Oded Goldreich, Hugo Krawczyk, Michael Luby
1993 J jnl
Randomness in Interactive Proofs.
Comput. Complex.
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
1992 A* conf
Approximations of General Independent Distributions
STOC
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
1992 J jnl
Critique of some trends in the TCS community in light of two controversies.
SIGACT News
Oded Goldreich
1992 A* conf
On Defining Proofs of Knowledge.
CRYPTO
Mihir Bellare, Oded Goldreich
1992 A* conf
On the Complexity of Global Computation in the Presence of Link Failures: The Case of Uni-Directional Faults.
PODC
Oded Goldreich, Dror Sneh
1992 J jnl
On the Theory of Average Case Complexity.
J. Comput. Syst. Sci.
Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby
1992 J jnl
On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization.
J. Comput. Syst. Sci.
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai
1992 J jnl
Simple Construction of Almost k-wise Independent Random Variables.
Random Struct. Algorithms
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
1992 J jnl
Sparse Pseudorandom Distributions.
Random Struct. Algorithms
Oded Goldreich, Hugo Krawczyk
1992 A* conf
Towards a Computational Theory of Statistical Tests (Extended Abstract)
FOCS
Manuel Blum, Oded Goldreich
1991 J jnl
Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.
Distributed Comput.
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai
1991 A* conf
Fault-tolerant Computation in the Full Information Model (Extended Abstract)
FOCS
Oded Goldreich, Shafi Goldwasser, Nathan Linial
1991 J jnl
On the Complexity of Computation in the Presence of Link Failures: The Case of a Ring.
Distributed Comput.
Oded Goldreich, Liuba Shrira
1991 J jnl
Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems.
J. ACM
Oded Goldreich, Silvio Micali, Avi Wigderson
1991 A* conf
Quantifying Knowledge Complexity
FOCS
Oded Goldreich, Erez Petrank
1990 J jnl
A Note on Computational Indistinguishability.
Inf. Process. Lett.
Oded Goldreich
1990 A* conf
A Quantitative Approach to Dynamic Networks.
PODC
Baruch Awerbuch, Oded Goldreich, Amir Herzberg
1990 J jnl
A Trade-Off between Information and Communication in Broadcast Protocols
J. ACM
Baruch Awerbuch, Oded Goldreich, David Peleg, Ronen Vainish
1990 J jnl
A fair protocol for signing contracts.
IEEE Trans. Inf. Theory
Michael Ben-Or, Oded Goldreich, Silvio Micali, Ronald L. Rivest
1990 J jnl
An Improved Parallel Algorithm for Integer GCD.
Algorithmica
Benny Chor, Oded Goldreich
1990 A* conf
Bounds on Tradeoffs between Randomness and Communication Complexity
FOCS
Ran Canetti, Oded Goldreich
1990 A* conf
On the Composition of Zero-Knowledge Proof Systems.
ICALP
Oded Goldreich, Hugo Krawczyk
1990 J jnl
On the number of monochromatic close pairs of beads in a rosary.
Discret. Math.
Oded Goldreich
1990 A* conf
Randomness in Interactive Proofs
FOCS
Mihir Bellare, Oded Goldreich, Shafi Goldwasser
1990 A* conf
Security Preserving Amplification of Hardness
FOCS
Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman
1990 A* conf
Simple Constructions of Almost k-Wise Independent Random Variables
FOCS
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
1990 J jnl
The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols.
Inf. Process. Lett.
Oded Goldreich, Erez Petrank
1989 A* conf
A Hard-Core Predicate for all One-Way Functions
STOC
Oded Goldreich, Leonid A. Levin
1989 — conf
Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection.
WDAG
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai
1989 J jnl
On Completeness and Soundness in Interactive Proof Systems.
Adv. Comput. Res.
Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos
1989 A* conf
On the Theory of Average Case Complexity
STOC
Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby
1989 — conf
On the Theory of Average Case Complexity (abstract).
SCT
Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby
1989 J jnl
On the power of two-point based sampling.
J. Complex.
Benny Chor, Oded Goldreich
1989 A* conf
On-Line/Off-Line Digital Schemes.
CRYPTO
Shimon Even, Oded Goldreich, Silvio Micali
1989 A* conf
Source to Destination Communication in the Presence of Faults.
PODC
Oded Goldreich, Amir Herzberg, Yishay Mansour
1989 A* conf
Sparse Pseudorandom Distributions.
CRYPTO
Oded Goldreich, Hugo Krawczyk
1988 A* conf
A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm.
CRYPTO
Oded Goldreich, Eyal Kushilevitz
1988 — conf
A Tradeoff between Information and Communication in Broadcast Protocols.
AWOC
Baruch Awerbuch, Oded Goldreich, David Peleg, Ronen Vainish
1988 A* conf
Everything Provable is Provable in Zero-Knowledge.
CRYPTO
Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, Phillip Rogaway
1988 A* conf
On the Existence of Pseudorandom Generators (Extended Abstract)
FOCS
Oded Goldreich, Hugo Krawczyk, Michael Luby
1988 A* conf
On the Existence of Pseudorandom Generators.
CRYPTO
Oded Goldreich, Hugo Krawczyk, Michael Luby
1988 J jnl
RSA and Rabin Functions: Certain Parts are as Hard as the Whole.
SIAM J. Comput.
Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr
1988 J jnl
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity.
SIAM J. Comput.
Benny Chor, Oded Goldreich
1987 J jnl
Electing a Leader in a Ring with Link Failures.
Acta Informatica
Oded Goldreich, Liuba Shrira
1987 A* conf
How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority
STOC
Oded Goldreich, Silvio Micali, Avi Wigderson
1987 A* conf
How to Solve any Protocol Problem - An Efficiency Improvement.
CRYPTO
Oded Goldreich, Ronen Vainish
1987 A* conf
Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract)
FOCS
Oded Goldreich, Yishay Mansour, Michael Sipser
1987 A* conf
On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization.
PODC
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai
1987 A* conf
Towards a Theory of Software Protection and Simulation by Oblivious RAMs
STOC
Oded Goldreich
1986 A* conf
How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design.
CRYPTO
Oded Goldreich, Silvio Micali, Avi Wigderson
1986 J jnl
How to construct random functions.
J. ACM
Oded Goldreich, Shafi Goldwasser, Silvio Micali
1986 B conf
Proofs that Release Minimum Knowledge.
MFCS
Oded Goldreich, Silvio Micali, Avi Wigderson
1986 A* conf
Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)
FOCS
Oded Goldreich, Silvio Micali, Avi Wigderson
1986 A* conf
The Effect of Link Failures on Computations in Asynchronous Rings.
PODC
Oded Goldreich, Liuba Shrira
1986 A* conf
Towards a Theory of Software Protection.
CRYPTO
Oded Goldreich
1986 A* conf
Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme.
CRYPTO
Oded Goldreich
1985 A* conf
A Fair Protocol for Signing Contracts (Extended Abstract).
ICALP
Michael Ben-Or, Oded Goldreich, Silvio Micali, Ronald L. Rivest
1985 J jnl
A Randomized Protocol for Signing Contracts.
Commun. ACM
Shimon Even, Oded Goldreich, Abraham Lempel
1985 J jnl
On the Power of Cascade Ciphers
ACM Trans. Comput. Syst.
Shimon Even, Oded Goldreich
1985 A* conf
On the Security of Ping-Pong Protocols when Implemented using the RSA.
CRYPTO
Shimon Even, Oded Goldreich, Adi Shamir
1985 A* conf
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)
FOCS
Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky
1985 A* conf
The Bit Security of Modular Squaring Given Partial Factorization of the Modulos.
CRYPTO
Benny Chor, Oded Goldreich, Shafi Goldwasser
1985 A* conf
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract)
FOCS
Benny Chor, Oded Goldreich
1984 J jnl
Correction to 'DES-like functions can generate the alternating group' (Nov 83 863-865).
IEEE Trans. Inf. Theory
Shimon Even, Oded Goldreich
1984 A* conf
How to Construct Random Functions (Extended Abstract)
FOCS
Oded Goldreich, Shafi Goldwasser, Silvio Micali
1984 A* conf
On Concurrent Identification Protocols.
EUROCRYPT
Oded Goldreich
1984 A* conf
On the Cryptographic Applications of Random Functions.
CRYPTO
Oded Goldreich, Shafi Goldwasser, Silvio Micali
1984 A* conf
On the Number of Close-and-Equal Pairs of Bits in a String.
EUROCRYPT
Oded Goldreich
1984 J jnl
On the np-completeness of certain network testing problems.
Networks
Shimon Even, Oded Goldreich, Shlomo Moran, Po Tong
1984 A* conf
RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure
FOCS
Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr
1984 A* conf
RSA/Rabin Least Significant Bits are 1/2 + 1/(poly(log N)) Secure.
CRYPTO
Benny Chor, Oded Goldreich
1983 A* conf
A Simple Protocol for Signing Contracts.
CRYPTO
Oded Goldreich
1983 J jnl
DES-like functions can generate the alternating group.
IEEE Trans. Inf. Theory
Shimon Even, Oded Goldreich
1983 A* conf
Electronic Wallet.
CRYPTO
Shimon Even, Oded Goldreich
1983 A* conf
On the Power of Cascade Ciphers.
CRYPTO
Shimon Even, Oded Goldreich
1983 A* conf
On the Security of Multi-Party Ping-Pong Protocols
FOCS
Shimon Even, Oded Goldreich
1982 A* conf
A Randomized Protocol for Signing Contracts.
CRYPTO
Shimon Even, Oded Goldreich, Abraham Lempel
1982 A* conf
On the Security of Multi-Party Ping-Pong Protocols.
CRYPTO
Shimon Even, Oded Goldreich
1981 J jnl
The Minimum-Length Generator Sequence Problem is NP-Hard.
J. Algorithms
Shimon Even, Oded Goldreich