Google
Google Scholar
Semantic Scholar
MS Academic
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
- 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)- [c138]Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Computational Complexity Conference 2021: 12:1-12:74 - [c137]Marshall Ball, Oded Goldreich, Tal Malkin:
Communication Complexity with Defective Randomness. Computational Complexity Conference 2021: 14:1-14:10 - [i165]Oded Goldreich:
Robust Self-Ordering versus Local Self-Ordering. Electron. Colloquium Comput. Complex. 28: 34 (2021) - [i164]Oded Goldreich:
Open Problems in Property Testing of Graphs. Electron. Colloquium Comput. Complex. 28: 88 (2021) - [i163]Oded Goldreich, Dana Ron:
A Lower Bound on the Complexity of Testing Grained Distributions. Electron. Colloquium Comput. Complex. 28: 129 (2021) - [i162]Oded Goldreich, Dana Ron:
Testing Distributions of Huge Objects. Electron. Colloquium Comput. Complex. 28: 133 (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. 27: 54 (2020) - [i160]Oded Goldreich, Dana Ron:
One-Sided Error Testing of Monomials and Affine Subspaces. Electron. Colloquium Comput. Complex. 27: 68 (2020) - [i159]Oded Goldreich:
On Counting $t$-Cliques Mod 2. Electron. Colloquium Comput. Complex. 27: 104 (2020) - [i158]Oded Goldreich:
On Testing Hamiltonicity in the Bounded Degree Graph Model. Electron. Colloquium Comput. Complex. 27: 109 (2020) - [i157]Oded Goldreich:
On Testing Asymmetry in the Bounded Degree Graph Model. Electron. Colloquium Comput. Complex. 27: 118 (2020) - [i156]Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Electron. Colloquium Comput. Complex. 27: 149 (2020) - [i155]Oded Goldreich, Avi Wigderson:
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. Electron. Colloquium Comput. Complex. 27: 160 (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. 27: 192 (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]Oded Goldreich:
Multi-pseudodeterministic algorithms. Electron. Colloquium Comput. Complex. 26: 12 (2019) - [i151]Itai Benjamini, Oded Goldreich:
Pseudo-Mixing Time of Random Walks. Electron. Colloquium Comput. Complex. 26: 78 (2019) - [i150]Oded Goldreich:
On the Complexity of Estimating the Effective Support Size. Electron. Colloquium Comput. Complex. 26: 88 (2019) - [i149]Oded Goldreich:
Testing Isomorphism in the Bounded-Degree Graph Model. Electron. Colloquium Comput. Complex. 26: 102 (2019) - [i148]Oded Goldreich:
Improved bounds on the AN-complexity of multilinear functions. Electron. Colloquium Comput. Complex. 26: 171 (2019) - [i147]Marshall Ball, Oded Goldreich, Tal Malkin:
Randomness Extraction from Somewhat Dependent Sources. Electron. Colloquium Comput. Complex. 26: 183 (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]Oded Goldreich, Dana Ron:
The Subgraph Testing Model. Electron. Colloquium Comput. Complex. 25: 45 (2018) - [i145]Oded Goldreich, Guy N. Rothblum:
Counting t-cliques: Worst-case to average-case reductions and Direct interactive proof systems. Electron. Colloquium Comput. Complex. 25: 46 (2018) - [i144]Irit Dinur, Oded Goldreich, Tom Gur:
Every set in P is strongly testable under a suitable encoding. Electron. Colloquium Comput. Complex. 25: 50 (2018) - [i143]Oded Goldreich, Guy N. Rothblum:
Constant-round interactive proof systems for AC0[2] and NC1. Electron. Colloquium Comput. Complex. 25: 69 (2018) - [i142]Oded Goldreich:
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. Electron. Colloquium Comput. Complex. 25: 98 (2018) - [i141]Oded Goldreich:
Flexible models for testing graph properties. Electron. Colloquium Comput. Complex. 25: 104 (2018) - [i140]Oded Goldreich:
Testing Graphs in Vertex-Distribution-Free Models. Electron. Colloquium Comput. Complex. 25: 171 (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, Guy N. Rothblum:
Simple doubly-efficient interactive proof systems for locally-characterizable sets. Electron. Colloquium Comput. Complex. 24: 18 (2017) - [i138]Oded Goldreich:
On the doubly-efficient interactive proof systems of GKR. Electron. Colloquium Comput. Complex. 24: 101 (2017) - [i137]Oded Goldreich:
Overview of the doubly-efficient interactive proof systems of RRR. Electron. Colloquium Comput. Complex. 24: 102 (2017) - [i136]Oded Goldreich, Guy N. Rothblum:
Worst-case to Average-case reductions for subclasses of P. Electron. Colloquium Comput. Complex. 24: 130 (2017) - [i135]Oded Goldreich, Avishay Tal:
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. 24: 193 (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. 23: 15 (2016) - [i133]Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. Electron. Colloquium Comput. Complex. 23: 42 (2016) - [i132]Oded Goldreich, Maya Leshkowitz:
On Emulating Interactive Proofs with Public Coins. Electron. Colloquium Comput. Complex. 23: 66 (2016) - [i131]Oded Goldreich:
Reducing testing affine spaces to testing linearity. Electron. Colloquium Comput. Complex. 23: 80 (2016) - [i130]Oded Goldreich:
Deconstructing 1-local expanders. Electron. Colloquium Comput. Complex. 23: 152 (2016) - [i129]Oded Goldreich, Tom Gur:
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP. Electron. Colloquium Comput. Complex. 23: 192 (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. Computational Complexity Conference 2015: 1-41 - [c129]Oded Goldreich, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. Computational Complexity Conference 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, Emanuele Viola, Avi Wigderson:
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. 22: 3 (2015) - [i127]Oded Goldreich, Tom Gur, Ron Rothblum:
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs. Electron. Colloquium Comput. Complex. 22: 24 (2015) - [i126]Oded Goldreich, Avishay Tal:
Matrix Rigidity of Random Toeplitz Matrices. Electron. Colloquium Comput. Complex. 22: 79 (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. 21: 25 (2014) - [i124]Oded Goldreich, Dana Ron:
On Learning and Testing Dynamic Environments. Electron. Colloquium Comput. Complex. 21: 29 (2014) - [i123]Oded Goldreich, Liav Teichner:
Super-Perfect Zero-Knowledge Proofs. Electron. Colloquium Comput. Complex. 21: 97 (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, Avi Wigderson:
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. 20: 43 (2013) - [i121]Oded Goldreich:
On Multiple Input Problems in Property Testing. Electron. Colloquium Comput. Complex. 20: 67 (2013) - [i120]Oded Goldreich:
On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing. Electron. Colloquium Comput. Complex. 20: 73 (2013) - [i119]Oded Goldreich, Dana Ron:
On Sample-Based Testers. Electron. Colloquium Comput. Complex. 20: 109 (2013) - [i118]Oded Goldreich, Avi Wigderson:
On Derandomizing Algorithms that Err Extremely Rarely. Electron. Colloquium Comput. Complex. 20: 152 (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]Oded Goldreich:
On the Effect of the Proximity Parameter on Property Testers. Electron. Colloquium Comput. Complex. 19: 12 (2012) - [i116]Oded Goldreich:
Two-Sided Error Proximity Oblivious Testing. Electron. Colloquium Comput. Complex. 19: 21 (2012) - [i115]Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding Cycles and Trees in Sublinear Time. Electron. Colloquium Comput. Complex. 19: 35 (2012) - [i114]Oded Goldreich, Shafi Goldwasser, Dana Ron:
On the possibilities and limitations of pseudodeterministic algorithms. Electron. Colloquium Comput. Complex. 19: 101 (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