Stop the war!Остановите войну!
for scientists:
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
- 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 - [i171]Oded Goldreich, Dana Ron:
Testing Distributions of Huge Objects. CoRR abs/2212.12802 (2022) - [i170]Oded Goldreich, Guy N. Rothblum, Tal Skverer:
On Interactive Proofs of Proximity with Proof-Oblivious Queries. 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. Computational Complexity Conference 2021: 12:1-12:74 - [c138]Marshall Ball, Oded Goldreich, Tal Malkin:
Communication Complexity with Defective Randomness. Computational Complexity Conference 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. 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, 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]