default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDOded Goldreich 0001
Person information
- affiliation: Weizmann Institute of Science, Israel
- award (2017): Knuth Prize
Other persons with the same name
- Oded Goldreich 0002 — Bar Ilan University, Ramat Gan, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[i184]Oded Goldreich:
On locally-characterized expander graphs (a survey). Electron. Colloquium Comput. Complex. TR24 (2024)- [i183]Oded Goldreich:
On the query complexity of testing local graph properties in the bounded-degree graph model. Electron. Colloquium Comput. Complex. TR24 (2024) - [i182]Oded Goldreich:
On the relaxed LDC of BGHSV: A survey that corrects the record. Electron. Colloquium Comput. Complex. TR24 (2024) - [i181]Oded Goldreich:
On the Cook-Mertz Tree Evaluation procedure. Electron. Colloquium Comput. Complex. TR24 (2024) - [i180]Oded Goldreich:
Solving Tree Evaluation in o(log n · log log n) space. Electron. Colloquium Comput. Complex. TR24 (2024) - [i179]Noga Amir, Oded Goldreich, Guy N. Rothblum:
Doubly Sub-linear Interactive Proofs of Proximity. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [j122]Oded Goldreich, Dana Ron:
A Lower Bound on the Complexity of Testing Grained Distributions. Comput. Complex. 32(2): 11 (2023) - [j121]Oded Goldreich, Dana Ron:
Testing Distributions of Huge Objects. TheoretiCS 2 (2023) - [c142]Oded Goldreich, Guy N. Rothblum, Tal Skverer:
On Interactive Proofs of Proximity with Proof-Oblivious Queries. ITCS 2023: 59:1-59:16 - [i178]Oded Goldreich:
On teaching the approximation method for circuit lower bounds. Electron. Colloquium Comput. Complex. TR23 (2023) - [i177]Oded Goldreich:
On the Lower Bound on the Length of Relaxed Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR23 (2023) - [i176]Oded Goldreich:
On the complexity of enumerating ordered sets. Electron. Colloquium Comput. Complex. TR23 (2023) - [i175]Oded Goldreich:
On coarse and fine approximate counting of t-cliques. Electron. Colloquium Comput. Complex. TR23 (2023) - [i174]Oded Goldreich, Laliv Tauber:
On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model. Electron. Colloquium Comput. Complex. TR23 (2023) - [i173]Oded Goldreich, Laliv Tauber:
On Testing Group Properties. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j120]Oded Goldreich:
Improved bounds on the AN-complexity of O(1)-linear functions. Comput. Complex. 31(2): 7 (2022) - [j119]Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. TheoretiCS 1 (2022) - [c141]Marshall Ball
, Oded Goldreich, Tal Malkin:
Randomness Extraction from Somewhat Dependent Sources. ITCS 2022: 12:1-12:14 - [c140]Oded Goldreich, Dana Ron:
Testing Distributions of Huge Objects. ITCS 2022: 78:1-78:19 - [i172]Oded Goldreich, Dana Ron:
Testing Distributions of Huge Objects. CoRR abs/2212.12802 (2022) - [i171]Oded Goldreich, Guy N. Rothblum, Tal Skverer:
On Interactive Proofs of Proximity with Proof-Oblivious Queries. Electron. Colloquium Comput. Complex. TR22 (2022) - [i170]Oded Goldreich, Laliv Tauber:
Testing in the bounded-degree graph model with degree bound two. Electron. Colloquium Comput. Complex. TR22 (2022) - [i169]Nader H. Bshouty, Oded Goldreich:
On properties that are non-trivial to test. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j118]Oded Goldreich, Tom Gur:
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Theor. Comput. Sci. 878-879: 83-101 (2021) - [c139]Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. CCC 2021: 12:1-12:74 - [c138]Marshall Ball, Oded Goldreich, Tal Malkin:
Communication Complexity with Defective Randomness. CCC 2021: 14:1-14:10 - [c137]Oded Goldreich, Avi Wigderson:
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. FOCS 2021: 269-275 - [i168]Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. CoRR abs/2112.00673 (2021) - [i167]Oded Goldreich:
Robust Self-Ordering versus Local Self-Ordering. Electron. Colloquium Comput. Complex. TR21 (2021) - [i166]Oded Goldreich:
Open Problems in Property Testing of Graphs. Electron. Colloquium Comput. Complex. TR21 (2021) - [i165]Oded Goldreich:
On the Locally Testable Code of Dinur et al. (2021). Electron. Colloquium Comput. Complex. TR21 (2021) - [i164]Oded Goldreich:
The KW Games as a Teaser. Electron. Colloquium Comput. Complex. TR21 (2021) - [i163]Oded Goldreich, Dana Ron:
A Lower Bound on the Complexity of Testing Grained Distributions. Electron. Colloquium Comput. Complex. TR21 (2021) - [i162]Oded Goldreich, Dana Ron:
Testing Distributions of Huge Objects. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j117]Oded Goldreich, Dana Ron:
The Subgraph Testing Model. ACM Trans. Comput. Theory 12(4): 28:1-28:32 (2020) - [p73]Scott E. Decatur, Oded Goldreich, Dana Ron:
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy. Computational Complexity and Property Testing 2020: 1-8 - [p72]Oded Goldreich, Or Meir:
Bridging a Small Gap in the Gap Amplification of Assignment Testers. Computational Complexity and Property Testing 2020: 9-16 - [p71]Oded Goldreich:
On (Valiant's) Polynomial-Size Monotone Formula for Majority. Computational Complexity and Property Testing 2020: 17-23 - [p70]Oded Goldreich:
Two Comments on Targeted Canonical Derandomizers. Computational Complexity and Property Testing 2020: 24-35 - [p69]Oded Goldreich:
On the Effect of the Proximity Parameter on Property Testers. Computational Complexity and Property Testing 2020: 36-40 - [p68]Oded Goldreich, Avi Wigderson:
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. Computational Complexity and Property Testing 2020: 41-86 - [p67]Oded Goldreich:
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing. Computational Complexity and Property Testing 2020: 87-118 - [p66]Oded Goldreich, Liav Teichner:
Super-Perfect Zero-Knowledge Proofs. Computational Complexity and Property Testing 2020: 119-140 - [p65]Oded Goldreich, Dana Ron:
On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition). Computational Complexity and Property Testing 2020: 141-151 - [p64]Oded Goldreich:
The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution. Computational Complexity and Property Testing 2020: 152-172 - [p63]Oded Goldreich, Maya Leshkowitz:
On Emulating Interactive Proofs with Public Coins. Computational Complexity and Property Testing 2020: 178-198 - [p62]Oded Goldreich:
Reducing Testing Affine Spaces to Testing Linearity of Functions. Computational Complexity and Property Testing 2020: 199-219 - [p61]Oded Goldreich:
Deconstructing 1-Local Expanders. Computational Complexity and Property Testing 2020: 220-248 - [p60]Oded Goldreich, Guy N. Rothblum:
Worst-Case to Average-Case Reductions for Subclasses of P. Computational Complexity and Property Testing 2020: 249-295 - [p59]Oded Goldreich:
On the Optimal Analysis of the Collision Probability Tester (an Exposition). Computational Complexity and Property Testing 2020: 296-305 - [p58]Oded Goldreich, Avishay Tal:
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. Computational Complexity and Property Testing 2020: 306-325 - [p57]Oded Goldreich, Guy N. Rothblum:
Constant-Round Interactive Proof Systems for AC0[2] and NC1. Computational Complexity and Property Testing 2020: 326-351 - [p56]Oded Goldreich:
Flexible Models for Testing Graph Properties. Computational Complexity and Property Testing 2020: 352-362 - [p55]Itai Benjamini, Oded Goldreich:
Pseudo-mixing Time of Random Walks. Computational Complexity and Property Testing 2020: 363-373 - [p54]Oded Goldreich:
On Constructing Expanders for Any Number of Vertices. Computational Complexity and Property Testing 2020: 374-379 - [e5]Oded Goldreich:
Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation. Lecture Notes in Computer Science 12050, Springer 2020, ISBN 978-3-030-43661-2 [contents] - [i161]Marshall Ball, Oded Goldreich, Tal Malkin:
Communication Complexity with Defective Randomness. Electron. Colloquium Comput. Complex. TR20 (2020) - [i160]Oded Goldreich:
On Counting $t$-Cliques Mod 2. Electron. Colloquium Comput. Complex. TR20 (2020) - [i159]Oded Goldreich:
On Testing Hamiltonicity in the Bounded Degree Graph Model. Electron. Colloquium Comput. Complex. TR20 (2020) - [i158]Oded Goldreich:
On Testing Asymmetry in the Bounded Degree Graph Model. Electron. Colloquium Comput. Complex. TR20 (2020) - [i157]Oded Goldreich, Dana Ron:
One-Sided Error Testing of Monomials and Affine Subspaces. Electron. Colloquium Comput. Complex. TR20 (2020) - [i156]Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Electron. Colloquium Comput. Complex. TR20 (2020) - [i155]Oded Goldreich, Avi Wigderson:
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. Electron. Colloquium Comput. Complex. TR20 (2020) - [i154]Oded Goldreich, Avi Wigderson:
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j116]Oded Goldreich:
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. Comput. Complex. 28(4): 709-747 (2019) - [j115]Oded Goldreich, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. ACM Trans. Comput. Theory 11(3): 17:1-17:38 (2019) - [c136]Irit Dinur, Oded Goldreich, Tom Gur:
Every Set in P Is Strongly Testable Under a Suitable Encoding. ITCS 2019: 30:1-30:17 - [c135]Oded Goldreich, Dana Ron:
The Subgraph Testing Model. ITCS 2019: 37:1-37:19 - [c134]Oded Goldreich:
Testing graphs in vertex-distribution-free models. STOC 2019: 527-534 - [p53]Oded Goldreich:
Preface. Providing Sound Foundations for Cryptography 2019 - [p52]Oded Goldreich, Shafi Goldwasser, Silvio Micali:
How to construct random functions. Providing Sound Foundations for Cryptography 2019: 241-264 - [p51]Oded Goldreich, Silvio Micali, Avi Wigderson:
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. Providing Sound Foundations for Cryptography 2019: 285-306 - [p50]Oded Goldreich, Silvio Micali, Avi Wigderson:
How to play any mental game, or a completeness theorem for protocols with honest majority. Providing Sound Foundations for Cryptography 2019: 307-328 - [p49]Oded Goldreich:
On the foundations of cryptography. Providing Sound Foundations for Cryptography 2019: 411-496 - [p48]Oded Goldreich:
On the impact of cryptography on complexity theory. Providing Sound Foundations for Cryptography 2019: 497-526 - [p47]Oded Goldreich:
On some noncryptographic works of Goldwasser and Micali. Providing Sound Foundations for Cryptography 2019: 527-542 - [e4]Oded Goldreich:
Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali. ACM 2019, ISBN 978-1-4503-7266-4 [contents] - [i153]Oded Goldreich:
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model. CoRR abs/1905.03070 (2019) - [i152]Marshall Ball, Oded Goldreich, Tal Malkin:
Randomness Extraction from Somewhat Dependent Sources. Electron. Colloquium Comput. Complex. TR19 (2019) - [i151]Itai Benjamini, Oded Goldreich:
Pseudo-Mixing Time of Random Walks. Electron. Colloquium Comput. Complex. TR19 (2019) - [i150]Oded Goldreich:
Multi-pseudodeterministic algorithms. Electron. Colloquium Comput. Complex. TR19 (2019) - [i149]Oded Goldreich:
On the Complexity of Estimating the Effective Support Size. Electron. Colloquium Comput. Complex. TR19 (2019) - [i148]Oded Goldreich:
Testing Isomorphism in the Bounded-Degree Graph Model. Electron. Colloquium Comput. Complex. TR19 (2019) - [i147]Oded Goldreich:
Improved bounds on the AN-complexity of multilinear functions. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j114]Oded Goldreich, Avishay Tal:
Matrix rigidity of random Toeplitz matrices. Comput. Complex. 27(2): 305-350 (2018) - [j113]Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. Chic. J. Theor. Comput. Sci. 2018 (2018) - [j112]Oded Goldreich:
On Doubly-Efficient Interactive Proof Systems. Found. Trends Theor. Comput. Sci. 13(3): 158-246 (2018) - [j111]Oded Goldreich, Tom Gur, Ron D. Rothblum:
Proofs of proximity for context-free languages and read-once branching programs. Inf. Comput. 261: 175-201 (2018) - [c133]Oded Goldreich, Guy N. Rothblum:
Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems. FOCS 2018: 77-88 - [c132]Oded Goldreich, Guy N. Rothblum:
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets. ITCS 2018: 18:1-18:19 - [i146]Irit Dinur, Oded Goldreich, Tom Gur:
Every set in P is strongly testable under a suitable encoding. Electron. Colloquium Comput. Complex. TR18 (2018) - [i145]Oded Goldreich:
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. Electron. Colloquium Comput. Complex. TR18 (2018) - [i144]Oded Goldreich:
Flexible models for testing graph properties. Electron. Colloquium Comput. Complex. TR18 (2018) - [i143]Oded Goldreich:
Testing Graphs in Vertex-Distribution-Free Models. Electron. Colloquium Comput. Complex. TR18 (2018) - [i142]Oded Goldreich, Dana Ron:
The Subgraph Testing Model. Electron. Colloquium Comput. Complex. TR18 (2018) - [i141]Oded Goldreich, Guy N. Rothblum:
Counting t-cliques: Worst-case to average-case reductions and Direct interactive proof systems. Electron. Colloquium Comput. Complex. TR18 (2018) - [i140]Oded Goldreich, Guy N. Rothblum:
Constant-round interactive proof systems for AC0[2] and NC1. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [b6]Oded Goldreich:
Introduction to Property Testing. Cambridge University Press 2017, ISBN 978-1-107-19405-2, pp. 1-468 - [j110]Oded Goldreich, Dana Ron:
On Learning and Testing Dynamic Environments. J. ACM 64(3): 21:1-21:90 (2017) - [i139]Oded Goldreich:
On the doubly-efficient interactive proof systems of GKR. Electron. Colloquium Comput. Complex. TR17 (2017) - [i138]Oded Goldreich:
Overview of the doubly-efficient interactive proof systems of RRR. Electron. Colloquium Comput. Complex. TR17 (2017) - [i137]Oded Goldreich, Guy N. Rothblum:
Simple doubly-efficient interactive proof systems for locally-characterizable sets. Electron. Colloquium Comput. Complex. TR17 (2017) - [i136]Oded Goldreich, Guy N. Rothblum:
Worst-case to Average-case reductions for subclasses of P. Electron. Colloquium Comput. Complex. TR17 (2017) - [i135]Oded Goldreich, Avishay Tal:
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j109]Oded Goldreich:
Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword. Comput. Complex. 25(3): 563-565 (2016) - [j108]Oded Goldreich, Igor Shinkar:
Two-sided error proximity oblivious testing. Random Struct. Algorithms 48(2): 341-383 (2016) - [j107]Oded Goldreich, Dana Ron:
On Sample-Based Testers. ACM Trans. Comput. Theory 8(2): 7:1-7:54 (2016) - [c131]Oded Goldreich, Avishay Tal:
Matrix rigidity of random toeplitz matrices. STOC 2016: 91-104 - [r3]Oded Goldreich, Dana Ron:
Estimating Simple Graph Parameters in Sublinear Time. Encyclopedia of Algorithms 2016: 650-653 - [r2]Oded Goldreich, Dana Ron:
Testing Bipartiteness in the Dense-Graph Model. Encyclopedia of Algorithms 2016: 2212-2216 - [r1]Oded Goldreich, Dana Ron:
Testing Bipartiteness of Graphs in Sublinear Time. Encyclopedia of Algorithms 2016: 2216-2219 - [i134]Oded Goldreich:
The uniform distribution is complete with respect to testing identity to a fixed distribution. Electron. Colloquium Comput. Complex. TR16 (2016) - [i133]Oded Goldreich, Maya Leshkowitz:
On Emulating Interactive Proofs with Public Coins. Electron. Colloquium Comput. Complex. TR16 (2016) - [i132]Oded Goldreich:
Reducing testing affine spaces to testing linearity. Electron. Colloquium Comput. Complex. TR16 (2016) - [i131]Oded Goldreich:
Deconstructing 1-local expanders. Electron. Colloquium Comput. Complex. TR16 (2016) - [i130]Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. Electron. Colloquium Comput. Complex. TR16 (2016) - [i129]Oded Goldreich, Tom Gur:
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j106]Oded Goldreich, Or Meir:
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly. ACM Trans. Comput. Theory 7(4): 16:1-16:13 (2015) - [c130]Oded Goldreich, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. CCC 2015: 1-41 - [c129]Oded Goldreich, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. CCC 2015: 601-668 - [c128]Oded Goldreich, Tom Gur, Ron D. Rothblum:
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract). ICALP (1) 2015: 666-677 - [c127]Oded Goldreich, Dana Ron:
On Sample-Based Testers. ITCS 2015: 337-345 - [i128]Oded Goldreich, Tom Gur, Ron Rothblum:
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs. Electron. Colloquium Comput. Complex. TR15 (2015) - [i127]Oded Goldreich, Avishay Tal:
Matrix Rigidity of Random Toeplitz Matrices. Electron. Colloquium Comput. Complex. TR15 (2015) - [i126]Oded Goldreich, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j105]Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding cycles and trees in sublinear time. Random Struct. Algorithms 45(2): 139-184 (2014) - [c126]Oded Goldreich:
On Multiple Input Problems in Property Testing. APPROX-RANDOM 2014: 704-720 - [c125]Oded Goldreich, Dana Ron:
On Learning and Testing Dynamic Environments. FOCS 2014: 336-343 - [c124]Oded Goldreich, Avi Wigderson:
On derandomizing algorithms that err extremely rarely. STOC 2014: 109-118 - [i125]Oded Goldreich, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. Electron. Colloquium Comput. Complex. TR14 (2014) - [i124]Oded Goldreich, Dana Ron:
On Learning and Testing Dynamic Environments. Electron. Colloquium Comput. Complex. TR14 (2014) - [i123]Oded Goldreich, Liav Teichner:
Super-Perfect Zero-Knowledge Proofs. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j104]David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, Gil Segev:
More Constructions of Lossy and Correlation-Secure Trapdoor Functions. J. Cryptol. 26(1): 39-74 (2013) - [j103]Oded Goldreich, Ron D. Rothblum:
Enhancements of Trapdoor Permutations. J. Cryptol. 26(3): 484-512 (2013) - [c123]Oded Goldreich, Shafi Goldwasser, Dana Ron:
On the possibilities and limitations of pseudodeterministic algorithms. ITCS 2013: 127-138 - [p46]Oded Goldreich:
General Cryptographic Protocols: The Very Basics. Secure Multi-Party Computation 2013: 1-27 - [p45]Oded Goldreich:
A Short Tutorial of Zero-Knowledge. Secure Multi-Party Computation 2013: 28-60 - [i122]Oded Goldreich:
On Multiple Input Problems in Property Testing. Electron. Colloquium Comput. Complex. TR13 (2013) - [i121]Oded Goldreich:
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing. Electron. Colloquium Comput. Complex. TR13 (2013) - [i120]Oded Goldreich, Dana Ron:
On Sample-Based Testers. Electron. Colloquium Comput. Complex. TR13 (2013) - [i119]Oded Goldreich, Avi Wigderson:
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. TR13 (2013) - [i118]Oded Goldreich, Avi Wigderson:
On Derandomizing Algorithms that Err Extremely Rarely. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j102]Oded Goldreich, Salil P. Vadhan:
Special issue from RANDOM'09: Editors' Foreword. Comput. Complex. 21(1): 1 (2012) - [j101]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. Comput. Complex. 21(1): 129-192 (2012) - [j100]Oded Goldreich:
Invitation to complexity theory. XRDS 18(3): 18-22 (2012) - [j99]Oded Goldreich, Or Meir:
The tensor product of two good codes is not necessarily robustly testable. Inf. Process. Lett. 112(8-9): 351-355 (2012) - [j98]Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (im)possibility of obfuscating programs. J. ACM 59(2): 6:1-6:48 (2012) - [j97]Oded Goldreich, Brendan Juba, Madhu Sudan:
A theory of goal-oriented communication. J. ACM 59(2): 8:1-8:65 (2012) - [j96]Oded Goldreich:
On struggle and competition in scientic fields. SIGACT News 43(1): 43-60 (2012) - [j95]Oded Goldreich:
On intellectual and instrumental values in science. SIGACT News 43(2): 45-50 (2012) - [j94]Oded Goldreich, Rani Izsak:
Monotone Circuits: One-Way Functions versus Pseudorandom Generators. Theory Comput. 8(1): 231-238 (2012) - [c122]Oded Goldreich, Igor Shinkar:
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract). APPROX-RANDOM 2012: 565-578 - [i117]Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding Cycles and Trees in Sublinear Time. Electron. Colloquium Comput. Complex. TR12 (2012) - [i116]Oded Goldreich:
On the Effect of the Proximity Parameter on Property Testers. Electron. Colloquium Comput. Complex. TR12 (2012) - [i115]Oded Goldreich:
Two-Sided Error Proximity Oblivious Testing. Electron. Colloquium Comput. Complex. TR12 (2012) - [i114]Oded Goldreich, Shafi Goldwasser, Dana Ron:
On the possibilities and limitations of pseudodeterministic algorithms. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j93]Oded Goldreich, Dana Ron:
Algorithmic Aspects of Property Testing in the Dense Graphs Model. SIAM J. Comput. 40(2): 376-445 (2011) - [j92]Oded Goldreich, Dana Ron:
On Proximity-Oblivious Testing. SIAM J. Comput. 40(2): 534-566 (2011) - [c121]Lidor Avigad, Oded Goldreich:
Testing Graph Blow-Up. APPROX-RANDOM 2011: 389-399 - [c120]Oded Goldreich, Tali Kaufman:
Proximity Oblivious Testing and the Role of Invariances. APPROX-RANDOM 2011: 579-592 - [c119]Oded Goldreich, Brendan Juba, Madhu Sudan:
A theory of goal-oriented communication. PODC 2011: 299-300 - [p44]Oded Goldreich:
Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard. Studies in Complexity and Cryptography 2011: 1-5 - [p43]Mihir Bellare, Oded Goldreich:
Proving Computational Ability. Studies in Complexity and Cryptography 2011: 6-12 - [p42]Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. Studies in Complexity and Cryptography 2011: 13-25 - [p41]Oded Goldreich, Avi Wigderson:
On the Circuit Complexity of Perfect Hashing. Studies in Complexity and Cryptography 2011: 26-29 - [p40]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Collision-Free Hashing from Lattice Problems. Studies in Complexity and Cryptography 2011: 30-39 - [p39]Oded Goldreich, David Zuckerman:
Another Proof That BPP Í PH\mathcal{BPP}\subseteq \mathcal{PH} (and More). Studies in Complexity and Cryptography 2011: 40-53 - [p38]Oded Goldreich:
Strong Proofs of Knowledge. Studies in Complexity and Cryptography 2011: 54-58 - [p37]Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
Simplified Derandomization of BPP Using a Hitting Set Generator. Studies in Complexity and Cryptography 2011: 59-67 - [p36]Oded Goldreich, Dana Ron:
On Testing Expansion in Bounded-Degree Graphs. Studies in Complexity and Cryptography 2011: 68-75 - [p35]Oded Goldreich:
Candidate One-Way Functions Based on Expander Graphs. Studies in Complexity and Cryptography 2011: 76-87 - [p34]Oded Goldreich:
Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs. Studies in Complexity and Cryptography 2011: 88-97 - [p33]Oded Goldreich:
The GGM Construction Does NOT Yield Correlation Intractable Function Ensembles. Studies in Complexity and Cryptography 2011: 98-108 - [p32]Oded Goldreich, Madhu Sudan, Luca Trevisan:
From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography 2011: 109-113 - [p31]Mihir Bellare, Oded Goldreich:
On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge. Studies in Complexity and Cryptography 2011: 114-123 - [p30]Oded Goldreich:
On the Average-Case Complexity of Property Testing. Studies in Complexity and Cryptography 2011: 124-135 - [p29]Oded Goldreich:
A Candidate Counterexample to the Easy Cylinders Conjecture. Studies in Complexity and Cryptography 2011: 136-140 - [p28]Zvika Brakerski, Oded Goldreich:
From Absolute Distinguishability to Positive Distinguishability. Studies in Complexity and Cryptography 2011: 141-155 - [p27]Lidor Avigad, Oded Goldreich:
Testing Graph Blow-Up. Studies in Complexity and Cryptography 2011: 156-172 - [p26]Oded Goldreich, Tali Kaufman:
Proximity Oblivious Testing and the Role of Invariances. Studies in Complexity and Cryptography 2011: 173-190 - [p25]Oded Goldreich:
In a World of P=BPP. Studies in Complexity and Cryptography 2011: 191-232 - [p24]Oded Goldreich:
Notes on Levin's Theory of Average-Case Complexity. Studies in Complexity and Cryptography 2011: 233-247 - [p23]Oded Goldreich:
Three XOR-Lemmas - An Exposition. Studies in Complexity and Cryptography 2011: 248-272 - [p22]Oded Goldreich, Noam Nisan, Avi Wigderson:
On Yao's XOR-Lemma. Studies in Complexity and Cryptography 2011: 273-301 - [p21]Oded Goldreich:
A Sample of Samplers: A Computational Perspective on Sampling. Studies in Complexity and Cryptography 2011: 302-332 - [p20]Oded Goldreich:
Short Locally Testable Codes and Proofs. Studies in Complexity and Cryptography 2011: 333-372 - [p19]Oded Goldreich:
Bravely, Moderately: A Common Theme in Four Recent Works. Studies in Complexity and Cryptography 2011: 373-389 - [p18]Oded Goldreich, Salil P. Vadhan:
On the Complexity of Computational Problems Regarding Distributions. Studies in Complexity and Cryptography 2011: 390-405 - [p17]Oded Goldreich:
Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art. Studies in Complexity and Cryptography 2011: 406-421 - [p16]Oded Goldreich:
Average Case Complexity, Revisited. Studies in Complexity and Cryptography 2011: 422-450 - [p15]Oded Goldreich:
Basic Facts about Expander Graphs. Studies in Complexity and Cryptography 2011: 451-464 - [p14]Oded Goldreich:
A Brief Introduction to Property Testing. Studies in Complexity and Cryptography 2011: 465-469 - [p13]Oded Goldreich:
Introduction to Testing Graph Properties. Studies in Complexity and Cryptography 2011: 470-506 - [p12]Oded Goldreich:
Randomness and Computation. Studies in Complexity and Cryptography 2011: 507-539 - [p11]Oded Goldreich:
On Security Preserving Reductions - Revised Terminology. Studies in Complexity and Cryptography 2011: 540-546 - [p10]Oded Goldreich:
Contemplations on Testing Graph Properties. Studies in Complexity and Cryptography 2011: 547-554 - [p9]Oded Goldreich:
Another Motivation for Reducing the Randomness Complexity of Algorithms. Studies in Complexity and Cryptography 2011: 555-560 - [e3]Oded Goldreich:
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. Lecture Notes in Computer Science 6650, Springer 2011, ISBN 978-3-642-22669-4 [contents] - [i113]Oded Goldreich:
Two Comments on Targeted Canonical Derandomizers. Electron. Colloquium Comput. Complex. TR11 (2011) - [i112]Oded Goldreich, Rani Izsak:
Monotone Circuits: One-Way Functions versus Pseudorandom Generators. Electron. Colloquium Comput. Complex. TR11 (2011) - [i111]Oded Goldreich, Or Meir:
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly. Electron. Colloquium Comput. Complex. TR11 (2011) - [i110]Oded Goldreich, Ron Rothblum:
Enhancements of Trapdoor Permutations. Electron. Colloquium Comput. Complex. TR11 (2011) - [i109]Oded Goldreich, Salil P. Vadhan:
On the complexity of computational problems regarding distributions (a survey). Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [b5]Oded Goldreich:
P, NP, and NP-Completeness: The Basics of Complexity Theory. Cambridge University Press 2010, ISBN 978-0-521-12254-2 - [j91]Oded Goldreich, Or Sheffet:
On The Randomness Complexity of Property Testing. Comput. Complex. 19(1): 99-133 (2010) - [j90]Oded Goldreich:
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits. J. Cryptol. 23(1): 1-36 (2010) - [j89]Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
On the Implementation of Huge Random Objects. SIAM J. Comput. 39(7): 2761-2822 (2010) - [c118]Oded Goldreich:
On Testing Computability by Small Width OBDDs. APPROX-RANDOM 2010: 574-587 - [c117]David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, Gil Segev:
More Constructions of Lossy and Correlation-Secure Trapdoor Functions. Public Key Cryptography 2010: 279-295 - [c116]Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz:
Erratum for: on basing one-way functions on NP-hardness. STOC 2010: 795-796 - [p8]Oded Goldreich:
A Brief Introduction to Property Testing. Property Testing 2010: 1-5 - [p7]Oded Goldreich:
The Program of the Mini-Workshop. Property Testing 2010: 6-12 - [p6]Oded Goldreich:
Short Locally Testable Codes and Proofs: A Survey in Two Parts. Property Testing 2010: 65-104 - [p5]Oded Goldreich:
Introduction to Testing Graph Properties. Property Testing 2010: 105-141 - [p4]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. Property Testing 2010: 289-294 - [p3]Oded Goldreich, Dana Ron:
Algorithmic Aspects of Property Testing in the Dense Graphs Model. Property Testing 2010: 295-305 - [e2]Oded Goldreich:
Property Testing - Current Research and Surveys. Lecture Notes in Computer Science 6390, Springer 2010, ISBN 978-3-642-16366-1 [contents] - [i108]Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding Cycles and Trees in Sublinear Time. CoRR abs/1007.4230 (2010) - [i107]Oded Goldreich:
On Testing Computability by Small Width OBDDs. Electron. Colloquium Comput. Complex. TR10 (2010) - [i106]Oded Goldreich:
Introduction to Testing Graph Properties. Electron. Colloquium Comput. Complex. TR10 (2010) - [i105]Oded Goldreich:
In a World of P=BPP. Electron. Colloquium Comput. Complex. TR10 (2010) - [i104]Oded Goldreich, Tali Kaufman:
Proximity Oblivious Testing and the Role of Invariances. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j88]Oded Goldreich:
On our duties as scientists. SIGACT News 40(3): 53-59 (2009) - [c115]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. APPROX-RANDOM 2009: 504-519 - [c114]Oded Goldreich, Dana Ron:
Algorithmic Aspects of Property Testing in the Dense Graphs Model. APPROX-RANDOM 2009: 520-533 - [c113]Oded Goldreich, Dana Ron:
On proximity oblivious testing. STOC 2009: 141-150 - [i103]Zvika Brakerski, Oded Goldreich:
From absolute distinguishability to positive distinguishability. Electron. Colloquium Comput. Complex. TR09 (2009) - [i102]Oded Goldreich:
A Candidate Counterexample to the Easy Cylinders Conjecture. Electron. Colloquium Comput. Complex. TR09 (2009) - [i101]Oded Goldreich, Brendan Juba, Madhu Sudan:
A Theory of Goal-Oriented Communication. Electron. Colloquium Comput. Complex. TR09 (2009) - [i100]David Mandell Freeman, Oded Goldreich, Eike Kiltz, Alon Rosen, Gil Segev:
More Constructions of Lossy and Correlation-Secure Trapdoor Functions. IACR Cryptol. ePrint Arch. 2009: 590 (2009) - 2008
- [b4]Oded Goldreich:
Computational complexity - a conceptual perspective. Cambridge University Press 2008, ISBN 978-0-521-88473-0, pp. I-XXIV, 1-606 - [j87]Oded Goldreich:
Preface to the Special Issue from Random'06. Comput. Complex. 17(1): 1-2 (2008) - [j86]Oded Goldreich:
Probabilistic Proof Systems: A Primer. Found. Trends Theor. Comput. Sci. 3(1): 1-91 (2008) - [j85]Oded Goldreich, Dana Ron:
Approximating average parameters of graphs. Random Struct. Algorithms 32(4): 473-493 (2008) - [j84]Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. SIAM J. Comput. 38(5): 1661-1694 (2008) - [j83]Oded Goldreich:
Computational complexity: a conceptual perspective. SIGACT News 39(3): 35-39 (2008) - [i99]Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. Electron. Colloquium Comput. Complex. TR08 (2008) - [i98]Oded Goldreich, Dana Ron:
Algorithmic Aspects of Property Testing in the Dense Graphs Model. Electron. Colloquium Comput. Complex. TR08 (2008) - [i97]Oded Goldreich, Dana Ron:
On Proximity Oblivious Testing. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j82]Oded Goldreich, Salil P. Vadhan:
Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword. Comput. Complex. 16(4): 325-330 (2007) - [c112]Kfir Barhum, Oded Goldreich, Adi Shraibman:
On Approximating the Average Distance Between Points. APPROX-RANDOM 2007: 296-310 - [c111]Oded Goldreich, Or Sheffet:
On the Randomness Complexity of Property Testing. APPROX-RANDOM 2007: 509-524 - [c110]Oded Goldreich:
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits. TCC 2007: 174-193 - [i96]Oded Goldreich:
On the Average-Case Complexity of Property Testing. Electron. Colloquium Comput. Complex. TR07 (2007) - [i95]Oded Goldreich, Or Meir:
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable. Electron. Colloquium Comput. Complex. TR07 (2007) - [i94]Oded Goldreich, Or Sheffet:
On the randomness complexity of property testing. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j81]Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan:
Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complex. 15(3): 263-296 (2006) - [j80]Oded Goldreich, Madhu Sudan:
Locally testable codes and PCPs of almost-linear length. J. ACM 53(4): 558-655 (2006) - [j79]Oded Goldreich, Yehuda Lindell:
Session-Key Generation Using Human Passwords Only. J. Cryptol. 19(3): 241-340 (2006) - [j78]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput. 36(4): 889-974 (2006) - [j77]Oded Goldreich, Madhu Sudan:
Special Issue on Randomness and Complexity. SIAM J. Comput. 36(4) (2006) - [c109]Oded Goldreich, Dana Ron:
Approximating Average Parameters of Graphs. APPROX-RANDOM 2006: 363-374 - [c108]Oded Goldreich:
Concurrent Zero-Knowledge with Timing, Revisited. Essays in Memory of Shimon Even 2006: 27-87 - [c107]Oded Goldreich:
On Promise Problems: A Survey. Essays in Memory of Shimon Even 2006: 254-290 - [c106]Oded Goldreich:
On Teaching the Basics of Complexity Theory. Essays in Memory of Shimon Even 2006: 348-374 - [c105]Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz:
On basing one-way functions on NP-hardness. STOC 2006: 701-710 - [e1]Oded Goldreich, Arnold L. Rosenberg, Alan L. Selman:
Theoretical Computer Science, Essays in Memory of Shimon Even. Lecture Notes in Computer Science 3895, Springer 2006, ISBN 3-540-32880-7 [contents] - [i93]Mihir Bellare, Oded Goldreich:
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge. Electron. Colloquium Comput. Complex. TR06 (2006) - [i92]Oded Goldreich:
On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits. Electron. Colloquium Comput. Complex. TR06 (2006) - [i91]Oded Goldreich:
On Expected Probabilistic Polynomial-Time Adversaries - A suggestion for restricted definitions and their benefits. IACR Cryptol. ePrint Arch. 2006: 277 (2006) - [i90]Mihir Bellare, Oded Goldreich:
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge. IACR Cryptol. ePrint Arch. 2006: 359 (2006) - [i89]Oded Goldreich:
On Post-Modern Cryptography. IACR Cryptol. ePrint Arch. 2006: 461 (2006) - 2005
- [j76]Oded Goldreich:
Foundations of Cryptography - A Primer. Found. Trends Theor. Comput. Sci. 1(1) (2005) - [c104]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Short PCPs Verifiable in Polylogarithmic Time. CCC 2005: 120-134 - [i88]Oded Goldreich:
Contemplations on Testing Graph Properties. Sublinear Algorithms 2005 - [i87]Oded Goldreich, Dana Ron:
Approximating Average Parameters of Graphs. Sublinear Algorithms 2005 - [i86]Oded Goldreich:
Short Locally Testable Codes and Proofs (Survey). Electron. Colloquium Comput. Complex. TR05 (2005) - [i85]Oded Goldreich:
On Promise Problems (a survey in memory of Shimon Even [1935-2004]). Electron. Colloquium Comput. Complex. TR05 (2005) - [i84]Oded Goldreich, Dana Ron:
Approximating Average Parameters of Graphs. Electron. Colloquium Comput. Complex. TR05 (2005) - [i83]Oded Goldreich:
Bravely, Moderately: A Common Theme in Four Recent Results. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [b3]Oded Goldreich:
The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press 2004, ISBN 0-521-83084-2 - [j75]Ran Canetti, Oded Goldreich, Shai Halevi:
The random oracle methodology, revisited. J. ACM 51(4): 557-594 (2004) - [j74]Oded Goldreich:
Preface. J. Cryptol. 17(1): 1-3 (2004) - [c103]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust pcps of proximity, shorter pcps and applications to coding. STOC 2004: 1-10 - [c102]Ran Canetti, Oded Goldreich, Shai Halevi:
On the Random-Oracle Methodology as Applied to Length-Restricted Signature Schemes. TCC 2004: 40-57 - [p2]Oded Goldreich:
Preface to "Week Three: Randomness in Computation". Computational Complexity Theory 2004: 249-251 - [p1]Oded Goldreich:
Pseudorandomness - Part I. Computational Complexity Theory 2004: 253-285 - [i82]Oded Goldreich, Dana Ron:
On Estimating the Average Degree of a Graph. Electron. Colloquium Comput. Complex. TR04 (2004) - [i81]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust PCPs of Proximity, Shorter PCPs and Applications to Coding. Electron. Colloquium Comput. Complex. TR04 (2004) - [i80]Oded Goldreich, Madhu Sudan, Luca Trevisan:
From logarithmic advice to single-bit advice. Electron. Colloquium Comput. Complex. TR04 (2004) - [i79]Mihir Bellare, Oded Goldreich, Anton Mityagin:
The Power of Verification Queries in Message Authentication and Authenticated Encryption. IACR Cryptol. ePrint Arch. 2004: 309 (2004) - 2003
- [j73]Oded Goldreich:
Cryptography and cryptographic protocols. Distributed Comput. 16(2-3): 177-199 (2003) - [j72]Noga Alon, Oded Goldreich, Yishay Mansour:
Almost k-wise independence versus k-wise independence. Inf. Process. Lett. 88(3): 107-110 (2003) - [j71]Oded Goldreich, Vered Rosen:
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators. J. Cryptol. 16(2): 71-93 (2003) - [j70]Oded Goldreich, Luca Trevisan:
Three theorems regarding testing graph properties. Random Struct. Algorithms 23(1): 23-57 (2003) - [c101]Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
On the Implementation of Huge Random Objects. FOCS 2003: 68-79 - [c100]Eli Ben-Sasson, Oded Goldreich, Madhu Sudan:
Bounds on 2-Query Codeword Testing. RANDOM-APPROX 2003: 216-227 - [i78]Eli Ben-Sasson, Oded Goldreich, Madhu Sudan:
Bounds on 2-Query Codeword Testing. Electron. Colloquium Comput. Complex. TR03 (2003) - [i77]Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
On the Implementation of Huge Random Objects. Electron. Colloquium Comput. Complex. TR03 (2003) - [i76]Ran Canetti, Oded Goldreich, Shai Halevi:
On the random-oracle methodology as applied to length-restricted signature schemes. IACR Cryptol. ePrint Arch. 2003: 150 (2003) - 2002
- [j69]Oded Goldreich, Dana Ron:
Property Testing in Bounded Degree Graphs. Algorithmica 32(2): 302-343 (2002) - [j68]Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
On interactive proofs with a laconic prover. Comput. Complex. 11(1-2): 1-53 (2002) - [c99]Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan:
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. CCC 2002: 175-183 - [c98]Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. CCC 2002: 194-203 - [c97]Oded Goldreich:
Zero-Knowledge. FOCS 2002: 3- - [c96]Oded Goldreich, Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length. FOCS 2002: 13-22 - [c95]Oded Goldreich, Avi Wigderson:
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good. RANDOM 2002: 209-223 - [c94]Oded Goldreich:
Concurrent zero-knowledge with timing, revisited. STOC 2002: 332-340 - [i75]Oded Goldreich, Avi Wigderson:
Derandomization that is rarely wrong from short advice that is typically good. Electron. Colloquium Comput. Complex. TR02 (2002) - [i74]Oded Goldreich:
The GGM Construction does NOT yield Correlation Intractable Function Ensembles. Electron. Colloquium Comput. Complex. TR02 (2002) - [i73]Noga Alon, Oded Goldreich, Yishay Mansour:
Almost k-wise independence versus k-wise independence. Electron. Colloquium Comput. Complex. TR02 (2002) - [i72]Oded Goldreich, Vered Rosen:
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators. Electron. Colloquium Comput. Complex. TR02 (2002) - [i71]Oded Goldreich, Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length. Electron. Colloquium Comput. Complex. TR02 (2002) - [i70]Oded Goldreich:
Zero-Knowledge twenty years after its invention. Electron. Colloquium Comput. Complex. TR02 (2002) - [i69]Oded Goldreich, Yoad Lustig, Moni Naor:
On Chosen Ciphertext Security of Multiple Encryptions. IACR Cryptol. ePrint Arch. 2002: 89 (2002) - [i68]Oded Goldreich:
The GGM Construction does NOT yield Correlation Intractable Function Ensembles. IACR Cryptol. ePrint Arch. 2002: 110 (2002) - [i67]Oded Goldreich:
Zero-Knowledge twenty years after its invention. IACR Cryptol. ePrint Arch. 2002: 186 (2002) - 2001
- [b2]Oded Goldreich:
The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press 2001, ISBN 0-521-79172-3 - [c93]Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (Im)possibility of Obfuscating Programs. CRYPTO 2001: 1-18 - [c92]Oded Goldreich, Yehuda Lindell:
Session-Key Generation Using Human Passwords Only. CRYPTO 2001: 408-432 - [c91]Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell:
Resettably-Sound Zero-Knowledge and its Applications. FOCS 2001: 116-125 - [c90]Oded Goldreich, Luca Trevisan:
Three Theorems Regarding Testing Graph Properties. FOCS 2001: 460-469 - [c89]Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
On Interactive Proofs with a Laconic Prover. ICALP 2001: 334-345 - [i66]Oded Goldreich, Luca Trevisan:
Three Theorems regarding Testing Graph Properties. Electron. Colloquium Comput. Complex. TR01 (2001) - [i65]Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
On Interactive Proofs with a Laconic Prover. Electron. Colloquium Comput. Complex. TR01 (2001) - [i64]Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (Im)possibility of Obfuscating Programs. Electron. Colloquium Comput. Complex. TR01 (2001) - [i63]Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan:
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. Electron. Colloquium Comput. Complex. TR01 (2001) - [i62]Oded Goldreich:
Concurrent Zero-Knowledge With Timing, Revisited. Electron. Colloquium Comput. Complex. TR01 (2001) - [i61]Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. Electron. Colloquium Comput. Complex. TR01 (2001) - [i60]Oded Goldreich:
Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs. Electron. Colloquium Comput. Complex. TR01 (2001) - [i59]Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell:
Resettably-Sound Zero-Knowledge and its Applications. IACR Cryptol. ePrint Arch. 2001: 63 (2001) - [i58]Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
On the (Im)possibility of Obfuscating Programs. IACR Cryptol. ePrint Arch. 2001: 69 (2001) - [i57]Oded Goldreich:
Concurrent Zero-Knowledge With Timing, Revisited. IACR Cryptol. ePrint Arch. 2001: 104 (2001) - [i56]Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. IACR Cryptol. ePrint Arch. 2001: 105 (2001) - 2000
- [j67]Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky:
Testing Monotonicity. Comb. 20(3): 301-337 (2000) - [j66]Mihir Bellare, Oded Goldreich, Erez Petrank:
Uniform Generation of NP-Witnesses Using an NP-Oracle. Inf. Comput. 163(2): 510-526 (2000) - [j65]Oded Goldreich, Shafi Goldwasser:
On the Limits of Nonapproximability of Lattice Problems. J. Comput. Syst. Sci. 60(3): 540-563 (2000) - [j64]Oded Goldreich:
Preface. J. Cryptol. 13(1): 1-7 (2000) - [j63]Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. SIAM J. Comput. 29(4): 1132-1154 (2000) - [j62]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discret. Math. 13(4): 535-570 (2000) - [j61]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese remaindering with errors. IEEE Trans. Inf. Theory 46(4): 1330-1338 (2000) - [c88]Oded Goldreich, Avi Wigderson:
On Pseudorandomness with respect to Deterministic Observes. ICALP Satellite Workshops 2000: 77-84 - [c87]Oded Goldreich:
Pseudorandomness. ICALP 2000: 687-704 - [c86]Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Resettable zero-knowledge (extended abstract). STOC 2000: 235-244 - [i55]Ran Canetti, Oded Goldreich, Shai Halevi:
The Random Oracle Methodology, Revisited. CoRR cs.CR/0010019 (2000) - [i54]Oded Goldreich, Salil P. Vadhan, Avi Wigderson:
Simplified derandomization of BPP using a hitting set generator. Electron. Colloquium Comput. Complex. TR00 (2000) - [i53]Oded Goldreich, Dana Ron:
On Testing Expansion in Bounded-Degree Graphs. Electron. Colloquium Comput. Complex. TR00 (2000) - [i52]Oded Goldreich, Avi Wigderson:
On Pseudorandomness with respect to Deterministic Observers. Electron. Colloquium Comput. Complex. TR00 (2000) - [i51]Oded Goldreich:
Candidate One-Way Functions Based on Expander Graphs. Electron. Colloquium Comput. Complex. TR00 (2000) - [i50]Oded Goldreich:
On Security Preserving Reductions - Revised Terminology. IACR Cryptol. ePrint Arch. 2000: 1 (2000) - [i49]Oded Goldreich, Yehuda Lindell:
Session-Key Generation using Human Passwords Only. IACR Cryptol. ePrint Arch. 2000: 57 (2000) - [i48]Oded Goldreich:
Candidate One-Way Functions Based on Expander Graphs. IACR Cryptol. ePrint Arch. 2000: 63 (2000) - [i47]Oded Goldreich, Vered Rosen:
On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators. IACR Cryptol. ePrint Arch. 2000: 64 (2000)
1990 – 1999
- 1999
- [j60]Oded Goldreich, Erez Petrank:
Quantifying Knowledge Complexity. Comput. Complex. 8(1): 50-98 (1999) - [j59]Oded Goldreich, Dana Ron:
A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Comb. 19(3): 335-373 (1999) - [j58]Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano:
The Graph Clustering Problem has a Perfect Zero-Knowledge Interactive Proof. Inf. Process. Lett. 69(4): 201-206 (1999) - [j57]Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert:
Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors. Inf. Process. Lett. 71(2): 55-61 (1999) - [j56]Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. J. Comput. Syst. Sci. 59(2): 253-269 (1999) - [j55]Scott E. Decatur, Oded Goldreich, Dana Ron:
Computational Sample Complexity. SIAM J. Comput. 29(3): 854-879 (1999) - [c85]Oded Goldreich, Salil P. Vadhan:
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. CCC 1999: 54- - [c84]Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson:
Deterministic Amplification of Space-Bounded Probabilistic Algorithms. CCC 1999: 188- - [c83]Mihir Bellare, Oded Goldreich, Hugo Krawczyk:
Stateless Evaluation of Pseudorandom Functions: Security beyond the Birthday Barrier. CRYPTO 1999: 270-287 - [c82]Oded Goldreich, Amit Sahai, Salil P. Vadhan:
Can Statistical Zero Knowledge Be Made Non-interactive? or On the Relationship of SZK and NISZK. CRYPTO 1999: 467-484 - [c81]Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity. RANDOM-APPROX 1999: 97-108 - [c80]Oded Goldreich, Avi Wigderson:
Improved Derandomization of BPP Using a Hitting Set Generator. RANDOM-APPROX 1999: 131-137 - [c79]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors. STOC 1999: 225-234 - [i46]Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert:
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors. Electron. Colloquium Comput. Complex. TR99 (1999) - [i45]Oded Goldreich, Amit Sahai, Salil P. Vadhan:
Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK. Electron. Colloquium Comput. Complex. TR99 (1999) - [i44]Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky:
Improved Testing Algorithms for Monotonicity. Electron. Colloquium Comput. Complex. TR99 (1999) - [i43]Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Interleaved Zero-Knowledge in the Public-Key Model. Electron. Colloquium Comput. Complex. TR99 (1999) - [i42]Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Resettable Zero-Knowledge. Electron. Colloquium Comput. Complex. TR99 (1999) - [i41]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors. IACR Cryptol. ePrint Arch. 1999: 2 (1999) - [i40]Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Interleaved Zero-Knowledge in the Public-Key Model. IACR Cryptol. ePrint Arch. 1999: 15 (1999) - [i39]Ran Canetti, Oded Goldreich, Shafi Goldwasser, Silvio Micali:
Resettable Zero-Knowledge. IACR Cryptol. ePrint Arch. 1999: 22 (1999) - 1998
- [b1]Oded Goldreich:
Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics 17, Springer 1998, ISBN 978-3-540-64766-9 - [j54]Oded Goldreich, Johan Håstad:
On the Complexity of Interactive Proofs with Bounded Communication. Inf. Process. Lett. 67(4): 205-214 (1998) - [j53]Oded Goldreich, Shafi Goldwasser, Dana Ron:
Property Testing and its Connection to Learning and Approximation. J. ACM 45(4): 653-750 (1998) - [j52]Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan:
Private Information Retrieval. J. ACM 45(6): 965-981 (1998) - [j51]Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic:
Efficient approximation of product distributions. Random Struct. Algorithms 13(1): 1-16 (1998) - [j50]Oded Goldreich, Shafi Goldwasser, Nathan Linial:
Fault-Tolerant Computation in the Full Information Model. SIAM J. Comput. 27(2): 506-544 (1998) - [j49]Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM J. Comput. 27(3): 804-915 (1998) - [j48]Oded Goldreich, Rafail Ostrovsky, Erez Petrank:
Computational Complexity and Knowledge Complexity. SIAM J. Comput. 27(4): 1116-1141 (1998) - [j47]Oded Goldreich, Bernd Meyer:
Computational Indistinguishability: Algorithms vs. Circuits. Theor. Comput. Sci. 191(1-2): 215-218 (1998) - [c78]Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. CCC 1998: 24-33 - [c77]Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest:
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop. CRYPTO 1998: 153-168 - [c76]Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron:
Testing Monotonicity. FOCS 1998: 426-435 - [c75]Oded Goldreich, Shafi Goldwasser:
On the Limits of Non-Approximability of Lattice Problems. STOC 1998: 1-9 - [c74]Ran Canetti, Oded Goldreich, Shai Halevi:
The Random Oracle Methodology, Revisited (Preliminary Version). STOC 1998: 209-218 - [c73]Oded Goldreich, Dana Ron:
A Sublinear Bipartiteness Tester for Bunded Degree Graphs. STOC 1998: 289-298 - [c72]Oded Goldreich, Amit Sahai, Salil P. Vadhan:
Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge. STOC 1998: 399-408 - [i38]Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano:
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof. Electron. Colloquium Comput. Complex. TR98 (1998) - [i37]Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. Electron. Colloquium Comput. Complex. TR98 (1998) - [i36]Mihir Bellare, Oded Goldreich, Erez Petrank:
Uniform Generation of NP-witnesses using an NP-oracle. Electron. Colloquium Comput. Complex. TR98 (1998) - [i35]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries - The Highly Noisy Case. Electron. Colloquium Comput. Complex. TR98 (1998) - [i34]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors. Electron. Colloquium Comput. Complex. TR98 (1998) - [i33]Oded Goldreich, Salil P. Vadhan:
Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK. Electron. Colloquium Comput. Complex. TR98 (1998) - [i32]Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson:
Deterministic Amplification of Space Bounded Probabilistic Algorithms. Electron. Colloquium Comput. Complex. TR98 (1998) - [i31]Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano:
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof. IACR Cryptol. ePrint Arch. 1998: 2 (1998) - [i30]Oded Goldreich, Shafi Goldwasser:
On the possibility of basing Cryptography on the assumption that P ≠ NP. IACR Cryptol. ePrint Arch. 1998: 5 (1998) - [i29]Ran Canetti, Oded Goldreich, Shai Halevi:
The Random Oracle Methodology, Revisited. IACR Cryptol. ePrint Arch. 1998: 11 (1998) - [i28]Oded Goldreich, Salil P. Vadhan:
Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK. IACR Cryptol. ePrint Arch. 1998: 26 (1998) - 1997
- [j46]Oded Goldreich, Dana Ron:
On Universal Learning Algorithms. Inf. Process. Lett. 63(3): 131-136 (1997) - [j45]Oded Goldreich, Avi Wigderson:
Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Struct. Algorithms 11(4): 315-343 (1997) - [j44]Oded Goldreich, Avi Wigderson:
Theory of computing: a scientific perspective (extended abstract). SIGACT News 28(3): 100-102 (1997) - [c71]Scott E. Decatur, Oded Goldreich, Dana Ron:
Computational Sample Complexity. COLT 1997: 130-142 - [c70]Oded Goldreich:
On the Foundations of Modern Cryptography. CRYPTO 1997: 46-74 - [c69]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem. CRYPTO 1997: 105-111 - [c68]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Public-Key Cryptosystems from Lattice Reduction Problems. CRYPTO 1997: 112-131 - [c67]Oded Goldreich:
Combinatorial property testing (a survey). Randomization Methods in Algorithm Design 1997: 45-59 - [c66]Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. RANDOM 1997: 67-84 - [c65]Oded Goldreich:
Probabilistic Proof Systems - A Survey. STACS 1997: 595-611 - [c64]Oded Goldreich, Dana Ron:
Property Testing in Bounded Degree Graphs. STOC 1997: 406-415 - [i27]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem. Electron. Colloquium Comput. Complex. TR97 (1997) - [i26]Oded Goldreich:
A Sample of Samplers - A Computational Perspective on Sampling (survey). Electron. Colloquium Comput. Complex. TR97 (1997) - [i25]Scott E. Decatur, Oded Goldreich, Dana Ron:
Computational Sample Complexity. Electron. Colloquium Comput. Complex. TR97 (1997) - [i24]Oded Goldreich, Shafi Goldwasser:
On the Limits of Non-Approximability of Lattice Problems. Electron. Colloquium Comput. Complex. TR97 (1997) - [i23]Oded Goldreich, David Zuckerman:
Another proof that BPP subseteq PH (and more). Electron. Colloquium Comput. Complex. TR97 (1997) - [i22]Oded Goldreich:
Combinatorial Property Testing (a survey). Electron. Colloquium Comput. Complex. TR97 (1997) - [i21]Oded Goldreich:
Notes on Levin's Theory of Average-Case Complexity. Electron. Colloquium Comput. Complex. TR97 (1997) - [i20]Scott E. Decatur, Oded Goldreich, Dana Ron:
A Probabilistic Error-Correcting Scheme. IACR Cryptol. ePrint Arch. 1997: 5 (1997) - [i19]Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest:
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop. IACR Cryptol. ePrint Arch. 1997: 12 (1997) - 1996
- [j43]Oded Goldreich, Avi Wigderson:
Theory of Computing: A Scientific Perspective. ACM Comput. Surv. 28(4es): 218 (1996) - [j42]Oded Goldreich, Rafail Ostrovsky:
Software Protection and Simulation on Oblivious RAMs. J. ACM 43(3): 431-473 (1996) - [j41]Shimon Even, Oded Goldreich, Silvio Micali:
On-Line/Off-Line Digital Signatures. J. Cryptol. 9(1): 35-67 (1996) - [j40]Oded Goldreich, Ariel Kahan:
How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptol. 9(3): 167-190 (1996) - [j39]Oded Goldreich, Hugo Krawczyk:
On the Composition of Zero-Knowledge Proof Systems. SIAM J. Comput. 25(1): 169-192 (1996) - [j38]Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser:
The future of computational complexity theory: part I. SIGACT News 27(3): 6-12 (1996) - [c63]Oded Goldreich, Shafi Goldwasser, Dana Ron:
Property Testing and Its Connection to Learning and Approximation. FOCS 1996: 339-348 - [c62]Ran Canetti, Uriel Feige, Oded Goldreich, Moni Naor:
Adaptively Secure Multi-Party Computation. STOC 1996: 639-648 - [i18]Oded Goldreich, Johan Håstad:
On the Message Complexity of Interactive Proof Systems. Electron. Colloquium Comput. Complex. TR96 (1996) - [i17]Oded Goldreich, Avi Wigderson:
On the Circuit Complexity of Perfect Hashing. Electron. Colloquium Comput. Complex. TR96 (1996) - [i16]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Collision-Free Hashing from Lattice Problems. Electron. Colloquium Comput. Complex. TR96 (1996) - [i15]Oded Goldreich, Shmuel Safra:
A Combinatorial Consistency Lemma with application to the PCP Theorem. Electron. Colloquium Comput. Complex. TR96 (1996) - [i14]Oded Goldreich:
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof. Electron. Colloquium Comput. Complex. TR96 (1996) - [i13]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Public-Key Cryptosystems from Lattice Reduction Problems. Electron. Colloquium Comput. Complex. TR96 (1996) - [i12]Oded Goldreich, Shafi Goldwasser, Dana Ron:
Property Testing and its connection to Learning and Approximation. Electron. Colloquium Comput. Complex. TR96 (1996) - [i11]Oded Goldreich, Bernd Meyer:
Computational Indistinguishability - Algorithms vs. Circuits. Electron. Colloquium Comput. Complex. TR96 (1996) - [i10]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Collision-Free Hashing from Lattice Problems. IACR Cryptol. ePrint Arch. 1996: 9 (1996) - [i9]Oded Goldreich:
The Graph Clustering Problem has a Perfect Zero-Knowledge Proof. IACR Cryptol. ePrint Arch. 1996: 14 (1996) - [i8]Oded Goldreich, Shafi Goldwasser, Shai Halevi:
Public-Key Cryptosystems from Lattice Reduction Problems. IACR Cryptol. ePrint Arch. 1996: 16 (1996) - 1995
- [j37]Ran Canetti, Guy Even, Oded Goldreich:
Lower Bounds for Sampling Algorithms for Estimating the Average. Inf. Process. Lett. 53(1): 17-25 (1995) - [c61]Ivan Damgård, Oded Goldreich, Tatsuaki Okamoto, Avi Wigderson:
Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs. CRYPTO 1995: 325-338 - [c60]Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan:
Private Information Retrieval. FOCS 1995: 41-50 - [c59]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case. FOCS 1995: 294-303 - [c58]Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCPs and Non-Approximability - Towards Tight Results. FOCS 1995: 422-431 - [c57]Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
Incremental cryptography and application to virus protection. STOC 1995: 45-56 - [i7]Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCP and Non-Approximability - Towards Tight Results. Electron. Colloquium Comput. Complex. TR95 (1995) - [i6]Oded Goldreich, Leonid A. Levin, Noam Nisan:
On Constructing 1-1 One-Way Functions. Electron. Colloquium Comput. Complex. TR95 (1995) - [i5]Oded Goldreich, Noam Nisan, Avi Wigderson:
On Yao's XOR-Lemma. Electron. Colloquium Comput. Complex. TR95 (1995) - [i4]Oded Goldreich:
Three XOR-Lemmas - An Exposition. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [j36]Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi:
The Random Oracle Hypothesis Is False. J. Comput. Syst. Sci. 49(1): 24-39 (1994) - [j35]Oded Goldreich, Yair Oren:
Definitions and Properties of Zero-Knowledge Proof Systems. J. Cryptol. 7(1): 1-32 (1994) - [j34]Oded Goldreich:
A taxonomy of proof systems (part 2). SIGACT News 25(1): 22-30 (1994) - [c56]Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
Incremental Cryptography: The Case of Hashing and Signing. CRYPTO 1994: 216-233 - [c55]Oded Goldreich, Rafail Ostrovsky, Erez Petrank:
Computational complexity and knowledge complexity (extended abstract). STOC 1994: 534-543 - [c54]Oded Goldreich, Avi Wigderson:
Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing. STOC 1994: 574-584 - [i3]Oded Goldreich, Avi Wigderson:
Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing. Electron. Colloquium Comput. Complex. TR94 (1994) - [i2]Oded Goldreich, Rafail Ostrovsky, Erez Petrank:
Computational Complexity and Knowledge Complexity. Electron. Colloquium Comput. Complex. TR94 (1994) - [i1]Oded Goldreich:
Probabilistic Proof Systems (A Survey). Electron. Colloquium Comput. Complex. TR94 (1994) - 1993
- [j33]Ran Canetti, Oded Goldreich:
Bounds on Tradeoffs Between Randomness and Communication Complexity. Comput. Complex. 3: 141-167 (1993) - [j32]Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
Randomness in Interactive Proofs. Comput. Complex. 3: 319-354 (1993) - [j31]Oded Goldreich:
A Uniform-Complexity Treatment of Encryption and Zero-Knowledge. J. Cryptol. 6(1): 21-53 (1993) - [j30]Oded Goldreich, Eyal Kushilevitz:
A Perfect Zero-Knowledge Proof System for a Problem Equivalent to the Discrete Logarithm. J. Cryptol. 6(2): 97-116 (1993) - [j29]Noga Alon, Oded Goldreich, Johan Håstad, René Peralta:
Addendum to "Simple Construction of Almost k-wise Independent Random Variables". Random Struct. Algorithms 4(1): 119-120 (1993) - [j28]Oded Goldreich, Hugo Krawczyk, Michael Luby:
On the Existence of Pseudorandom Generators. SIAM J. Comput. 22(6): 1163-1175 (1993) - [j27]Oded Goldreich:
A taxonomy of proof systems (part 1). SIGACT News 24(4): 2-13 (1993) - [c53]Michael Ben-Or, Ran Canetti, Oded Goldreich:
Asynchronous secure computation. STOC 1993: 52-61 - 1992
- [j26]Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby:
On the Theory of Average Case Complexity. J. Comput. Syst. Sci. 44(2): 193-219 (1992) - [j25]Reuven Bar-Yehuda, Oded Goldreich, Alon Itai:
On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization. J. Comput. Syst. Sci. 45(1): 104-126 (1992) - [j24]Oded Goldreich, Hugo Krawczyk:
Sparse Pseudorandom Distributions. Random Struct. Algorithms 3(2): 163-174 (1992) - [j23]Noga Alon, Oded Goldreich, Johan Håstad, René Peralta:
Simple Construction of Almost k-wise Independent Random Variables. Random Struct. Algorithms 3(3): 289-304 (1992) - [j22]Oded Goldreich:
Critique of some trends in the TCS community in light of two controversies. SIGACT News 23(1): 44-46 (1992) - [c52]Mihir Bellare, Oded Goldreich:
On Defining Proofs of Knowledge. CRYPTO 1992: 390-420 - [c51]Manuel Blum, Oded Goldreich:
Towards a Computational Theory of Statistical Tests (Extended Abstract). FOCS 1992: 406-416 - [c50]Oded Goldreich, Dror Sneh:
On the Complexity of Global Computation in the Presence of Link Failures: The Case of Uni-Directional Faults. PODC 1992: 103-111 - [c49]Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic:
Approximations of General Independent Distributions. STOC 1992: 10-16 - 1991
- [j21]Reuven Bar-Yehuda, Oded Goldreich, Alon Itai:
Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection. Distributed Comput. 5: 67-71 (1991) - [j20]Oded Goldreich, Liuba Shrira:
On the Complexity of Computation in the Presence of Link Failures: The Case of a Ring. Distributed Comput. 5: 121-131 (1991) - [j19]Oded Goldreich, Silvio Micali, Avi Wigderson:
Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM 38(3): 691-729 (1991) - [c48]Oded Goldreich, Erez Petrank:
Quantifying Knowledge Complexity. FOCS 1991: 59-68 - [c47]Oded Goldreich, Shafi Goldwasser, Nathan Linial:
Fault-tolerant Computation in the Full Information Model (Extended Abstract). FOCS 1991: 447-457 - 1990
- [j18]Benny Chor, Oded Goldreich:
An Improved Parallel Algorithm for Integer GCD. Algorithmica 5(1): 1-10 (1990) - [j17]Oded Goldreich:
On the number of monochromatic close pairs of beads in a rosary. Discret. Math. 80(1): 59-68 (1990) - [j16]Oded Goldreich:
A Note on Computational Indistinguishability. Inf. Process. Lett. 34(6): 277-281 (1990) - [j15]Oded Goldreich, Erez Petrank:
The Best of Both Worlds: Guaranteeing Termination in Fast Randomized Byzantine Agreement Protocols. Inf. Process. Lett. 36(1): 45-49 (1990) - [j14]Baruch Awerbuch, Oded Goldreich, David Peleg, Ronen Vainish:
A Trade-Off between Information and Communication in Broadcast Protocols. J. ACM 37(2): 238-256 (1990) - [j13]Michael Ben-Or, Oded Goldreich, Silvio Micali, Ronald L. Rivest:
A fair protocol for signing contracts. IEEE Trans. Inf. Theory 36(1): 40-46 (1990) - [c46]Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman:
Security Preserving Amplification of Hardness. FOCS 1990: 318-326 - [c45]Noga Alon, Oded Goldreich, Johan Håstad, René Peralta:
Simple Constructions of Almost k-Wise Independent Random Variables. FOCS 1990: 544-553 - [c44]Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
Randomness in Interactive Proofs. FOCS 1990: 563-572 - [c43]Ran Canetti, Oded Goldreich:
Bounds on Tradeoffs between Randomness and Communication Complexity. FOCS 1990: 766-775 - [c42]Oded Goldreich, Hugo Krawczyk:
On the Composition of Zero-Knowledge Proof Systems. ICALP 1990: 268-282 - [c41]Baruch Awerbuch, Oded Goldreich, Amir Herzberg:
A Quantitative Approach to Dynamic Networks. PODC 1990: 189-203
1980 – 1989
- 1989
- [j12]Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos:
On Completeness and Soundness in Interactive Proof Systems. Adv. Comput. Res. 5: 429-442 (1989) - [j11]Benny Chor, Oded Goldreich:
On the power of two-point based sampling. J. Complex. 5(1): 96-106 (1989) - [c40]Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby:
On the Theory of Average Case Complexity (abstract). SCT 1989: 36 - [c39]Oded Goldreich, Hugo Krawczyk:
Sparse Pseudorandom Distributions. CRYPTO 1989: 113-127 - [c38]Shimon Even, Oded Goldreich, Silvio Micali:
On-Line/Off-Line Digital Schemes. CRYPTO 1989: 263-275 - [c37]Oded Goldreich, Amir Herzberg, Yishay Mansour:
Source to Destination Communication in the Presence of Faults. PODC 1989: 85-101 - [c36]Oded Goldreich, Leonid A. Levin:
A Hard-Core Predicate for all One-Way Functions. STOC 1989: 25-32 - [c35]Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby:
On the Theory of Average Case Complexity. STOC 1989: 204-216 - [c34]Reuven Bar-Yehuda, Oded Goldreich, Alon Itai:
Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with no Collision Detection. WDAG 1989: 24-32 - 1988
- [j10]Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr:
RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM J. Comput. 17(2): 194-209 (1988) - [j9]Benny Chor, Oded Goldreich:
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. Comput. 17(2): 230-261 (1988) - [c33]Baruch Awerbuch, Oded Goldreich, David Peleg, Ronen Vainish:
A Tradeoff between Information and Communication in Broadcast Protocols. AWOC 1988: 369-379 - [c32]Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, Phillip Rogaway:
Everything Provable is Provable in Zero-Knowledge. CRYPTO 1988: 37-56 - [c31]Oded Goldreich, Eyal Kushilevitz:
A Perfect Zero-Knowledge Proof for a Problem Equivalent to Discrete Logarithm. CRYPTO 1988: 57-70 - [c30]Oded Goldreich, Hugo Krawczyk, Michael Luby:
On the Existence of Pseudorandom Generators. CRYPTO 1988: 146-162 - [c29]Oded Goldreich, Hugo Krawczyk, Michael Luby:
On the Existence of Pseudorandom Generators (Extended Abstract). FOCS 1988: 12-24 - 1987
- [j8]Oded Goldreich, Liuba Shrira:
Electing a Leader in a Ring with Link Failures. Acta Informatica 24(1): 79-91 (1987) - [c28]Oded Goldreich, Ronen Vainish:
How to Solve any Protocol Problem - An Efficiency Improvement. CRYPTO 1987: 73-86 - [c27]Oded Goldreich, Yishay Mansour, Michael Sipser:
Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract). FOCS 1987: 449-461 - [c26]Reuven Bar-Yehuda, Oded Goldreich, Alon Itai:
On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization. PODC 1987: 98-108 - [c25]Oded Goldreich:
Towards a Theory of Software Protection and Simulation by Oblivious RAMs. STOC 1987: 182-194 - [c24]Oded Goldreich, Silvio Micali, Avi Wigderson:
How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. STOC 1987: 218-229 - 1986
- [j7]Oded Goldreich, Shafi Goldwasser, Silvio Micali:
How to construct random functions. J. ACM 33(4): 792-807 (1986) - [c23]Oded Goldreich:
Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme. CRYPTO 1986: 104-110 - [c22]Oded Goldreich, Silvio Micali, Avi Wigderson:
How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design. CRYPTO 1986: 171-185 - [c21]Oded Goldreich:
Towards a Theory of Software Protection. CRYPTO 1986: 426-439 - [c20]Oded Goldreich, Silvio Micali, Avi Wigderson:
Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract). FOCS 1986: 174-187 - [c19]Oded Goldreich, Silvio Micali, Avi Wigderson:
Proofs that Release Minimum Knowledge. MFCS 1986: 639-650 - [c18]Oded Goldreich, Liuba Shrira:
The Effect of Link Failures on Computations in Asynchronous Rings. PODC 1986: 174-185 - 1985
- [j6]Shimon Even, Oded Goldreich, Abraham Lempel:
A Randomized Protocol for Signing Contracts. Commun. ACM 28(6): 637-647 (1985) - [j5]Shimon Even, Oded Goldreich:
On the Power of Cascade Ciphers. ACM Trans. Comput. Syst. 3(2): 108-116 (1985) - [c17]Shimon Even, Oded Goldreich, Adi Shamir:
On the Security of Ping-Pong Protocols when Implemented using the RSA. CRYPTO 1985: 58-72 - [c16]Benny Chor, Oded Goldreich, Shafi Goldwasser:
The Bit Security of Modular Squaring Given Partial Factorization of the Modulos. CRYPTO 1985: 448-457 - [c15]Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky:
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version). FOCS 1985: 396-407 - [c14]Benny Chor, Oded Goldreich:
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract). FOCS 1985: 429-442 - [c13]Michael Ben-Or, Oded Goldreich, Silvio Micali, Ronald L. Rivest:
A Fair Protocol for Signing Contracts (Extended Abstract). ICALP 1985: 43-52 - 1984
- [j4]Shimon Even, Oded Goldreich, Shlomo Moran, Po Tong:
On the np-completeness of certain network testing problems. Networks 14(1): 1-24 (1984) - [j3]Shimon Even, Oded Goldreich:
Correction to 'DES-like functions can generate the alternating group' (Nov 83 863-865). IEEE Trans. Inf. Theory 30(5): 780- (1984) - [c12]Oded Goldreich, Shafi Goldwasser, Silvio Micali:
On the Cryptographic Applications of Random Functions. CRYPTO 1984: 276-288 - [c11]Benny Chor, Oded Goldreich:
RSA/Rabin Least Significant Bits are 1/2 + 1/(poly(log N)) Secure. CRYPTO 1984: 303-313 - [c10]Oded Goldreich:
On the Number of Close-and-Equal Pairs of Bits in a String. EUROCRYPT 1984: 127-141 - [c9]Oded Goldreich:
On Concurrent Identification Protocols. EUROCRYPT 1984: 387-396 - [c8]Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr:
RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure. FOCS 1984: 449-457 - [c7]Oded Goldreich, Shafi Goldwasser, Silvio Micali:
How to Construct Random Functions (Extended Abstract). FOCS 1984: 464-479 - 1983
- [j2]Shimon Even, Oded Goldreich:
DES-like functions can generate the alternating group. IEEE Trans. Inf. Theory 29(6): 863-865 (1983) - [c6]Shimon Even, Oded Goldreich:
On the Power of Cascade Ciphers. CRYPTO 1983: 43-50 - [c5]Oded Goldreich:
A Simple Protocol for Signing Contracts. CRYPTO 1983: 133-136 - [c4]Shimon Even, Oded Goldreich:
Electronic Wallet. CRYPTO 1983: 383-386 - [c3]Shimon Even, Oded Goldreich:
On the Security of Multi-Party Ping-Pong Protocols. FOCS 1983: 34-39 - 1982
- [c2]Shimon Even, Oded Goldreich, Abraham Lempel:
A Randomized Protocol for Signing Contracts. CRYPTO 1982: 205-210 - [c1]Shimon Even, Oded Goldreich:
On the Security of Multi-Party Ping-Pong Protocols. CRYPTO 1982: 315 - 1981
- [j1]Shimon Even, Oded Goldreich:
The Minimum-Length Generator Sequence Problem is NP-Hard. J. Algorithms 2(3): 311-313 (1981)
Coauthor Index
[j122] [j121] [c140] [i172] [i163] [i162] [j117] [p73] [p65] [i157] [c135] [i142] [j110] [j107] [r3] [r2] [r1] [c127] [j105] [c125] [i124] [c123] [i120] [i117] [i114] [j93] [j92] [p36] [p3] [i108] [c114] [c113] [j85] [i98] [i97] [c109] [i87] [i84] [i82] [j69] [j67] [j61] [i53] [j59] [j55] [c81] [c79] [i44] [i41] [j53] [c76] [c73] [i34] [j46] [c71] [c64] [i25] [i20] [c63] [i12]
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-09-29 01:12 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
