Expert

Oded Goldreich

Scholar @ The Weizmann Institute Of Science

Israel |

About

Knuth Prize in 2017

Currently, his main research areas belong to the interplay of randomness and computation. Specific examples include:

The study of various notions of pseudorandomness.
The study of various types of probabilistic proof systems.
The study of property testing, a notion of approximation for decision problems

Paper list:
http://www.wisdom.weizmann.ac.il/~/oded/recent.html
https://scholar.google.com/citations?user=DLQW_LoAAAAJ

Interests

Probabilistic Proof Systems
Pseudorandomness
Property Testing
Foundations Of Cryptography

Google Presence

Projects

No Blockchain Project Yet

Papers

2019
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity
O Goldreich
computational complexity 28 (4), 709-747
1
2019
2019
Reducing testing affine spaces to testing linearity of functions
Reducing testing affine spaces to testing linearity of functions
O Goldreich
0
2019
2019
On constructing expanders for any number of vertices
On constructing expanders for any number of vertices
O Goldreich
0
2019
2019
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
O Goldreich, S Micali, A Wigderson
Providing Sound Foundations for Cryptography, 285-306
0
2019
2019
Providing Sound Foundations for Cryptography: On the work of Shafi Goldwasser and Silvio Micali
Providing Sound Foundations for Cryptography: On the work of Shafi Goldwasser and Silvio Micali
O Goldreich
Morgan & Claypool
0
2019
2019
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy
S Decatur, O Goldreich, D Ron
0
2019
2019
Bridging a Small Gap in the Gap Amplification of Assignment Testers
Bridging a Small Gap in the Gap Amplification of Assignment Testers
O Goldreich, O Meir
0
2019
2019
Testing Isomorphism in the Bounded-Degree Graph Model (preliminary version)
Testing Isomorphism in the Bounded-Degree Graph Model (preliminary version)
O Goldreich
0
2019
2019
Testing graphs in vertex-distribution-free models
Testing graphs in vertex-distribution-free models
O Goldreich
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …
4
2019
2019
On the Complexity of Estimating the Effective Support Size
On the Complexity of Estimating the Effective Support Size
O Goldreich
Electronic Colloquium on Computational Complexity (ECCC) 26, 88
0
2019
2019
Pseudo-Mixing Time of Random Walks
Pseudo-Mixing Time of Random Walks
I Benjamini, O Goldreich
0
2019
2019
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model
O Goldreich
arXiv preprint arXiv:1905.03070
0
2019
2019
On some non-cryptographic works of Goldwasser and Micali
On some non-cryptographic works of Goldwasser and Micali
O Goldreich
0
2019
2019
On the Impact of Cryptography on Complexity Theory
On the Impact of Cryptography on Complexity Theory
O Goldreich
0
2019
2019
Strong Locally Testable Codes with Relaxed Local Decoders
Strong Locally Testable Codes with Relaxed Local Decoders
O Goldreich, T Gur, I Komargodski
ACM Transactions on Computation Theory (TOCT) 11 (3), 17
1
2019
2019
Multi-pseudodeterministic algorithms.
Multi-pseudodeterministic algorithms.
O Goldreich
Electronic Colloquium on Computational Complexity (ECCC) 26, 12
1
2019
2018
Counting t-cliques: Worst-case to average-case reductions and Direct interactive proof systems
Counting t-cliques: Worst-case to average-case reductions and Direct interactive proof systems
O Goldreich, G Rothblum
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 77-88
8
2018
2018
Proofs of proximity for context-free languages and read-once branching programs
Proofs of proximity for context-free languages and read-once branching programs
O Goldreich, T Gur, RD Rothblum
Information and Computation 261, 175-201
16
2018
2018
Matrix rigidity of random toeplitz matrices
Matrix rigidity of random toeplitz matrices
O Goldreich, A Tal
computational complexity 27 (2), 305-350
12
2018
2018
Flexible models for testing graph properties.
Flexible models for testing graph properties.
O Goldreich
Electronic Colloquium on Computational Complexity (ECCC) 25, 104
2
2018
Read more

Google Trends (past one year)

25.2
Learn about Google Trends

Academic Achievement

89h-index
50.0KCitations

Popular People

Elaine Ou
Elaine Ou Writer @ The University of Sydney
Andrew DeSantis
Andrew DeSantis Investor | Entrepreneur | Programmer @ BTC Media | 21 Inc
Konstantinos (Kostas) Chalkias
Konstantinos (Kostas) Chalkias Programmer @ R3
Benedikt Bünz
Benedikt Bünz Scholar @ Stanford University | Applied Crypto Group
Craig Steven Wright
Craig Steven Wright Programmer | Entrepreneur @ nChain | DeMorgan
Browse all people