Oded Goldreich

ORCID

Publication Activity (10 Years)

Years Active: 1981-2024
Publications (10 Years): 84

Top Venues

Electron. Colloquium Comput. Complex.

ITCS

Comput. Complex.

ACM Trans. Comput. Theory

Publications

Oded Goldreich
On the Cook-Mertz Tree Evaluation procedure. Electron. Colloquium Comput. Complex. (2024)
Oded Goldreich
On the relaxed LDC of BGHSV: A survey that corrects the record. Electron. Colloquium Comput. Complex. (2024)
Oded Goldreich
space. Electron. Colloquium Comput. Complex. (2024)
Oded Goldreich
On the query complexity of testing local graph properties in the bounded-degree graph model. Electron. Colloquium Comput. Complex. (2024)
Oded Goldreich
On locally-characterized expander graphs (a survey). Electron. Colloquium Comput. Complex. (2024)
Oded Goldreich
On the complexity of enumerating ordered sets. Electron. Colloquium Comput. Complex. (2023)
Oded Goldreich
-cliques. Electron. Colloquium Comput. Complex. (2023)
Oded Goldreich, Laliv Tauber
On Testing Group Properties. Electron. Colloquium Comput. Complex. (2023)
Oded Goldreich
On the Lower Bound on the Length of Relaxed Locally Decodable Codes. Electron. Colloquium Comput. Complex. (2023)
Oded Goldreich, Laliv Tauber
On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model. Electron. Colloquium Comput. Complex. (2023)
Oded Goldreich
On teaching the approximation method for circuit lower bounds. Electron. Colloquium Comput. Complex. (2023)
Oded Goldreich, Guy N. Rothblum, Tal Skverer
On Interactive Proofs of Proximity with Proof-Oblivious Queries. ITCS (2023)
Oded Goldreich, Dana Ron
A Lower Bound on the Complexity of Testing Grained Distributions. Comput. Complex. 32 (2) (2023)
Oded Goldreich, Dana Ron
Testing Distributions of Huge Objects. TheoretiCS 2 (2023)
Nader H. Bshouty, Oded Goldreich
On properties that are non-trivial to test. Electron. Colloquium Comput. Complex. 29 (2022)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. TheoretiCS 1 (2022)
Oded Goldreich, Dana Ron
Testing Distributions of Huge Objects. CoRR (2022)
Oded Goldreich
Improved bounds on the AN-complexity of O(1)-linear functions. Comput. Complex. 31 (2) (2022)
Oded Goldreich, Guy N. Rothblum, Tal Skverer
On Interactive Proofs of Proximity with Proof-Oblivious Queries. Electron. Colloquium Comput. Complex. (2022)
Oded Goldreich, Laliv Tauber
Testing in the bounded-degree graph model with degree bound two. Electron. Colloquium Comput. Complex. (2022)
Oded Goldreich, Avi Wigderson
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. FOCS (2022)
Marshall Ball, Oded Goldreich, Tal Malkin
Randomness Extraction from Somewhat Dependent Sources. ITCS (2022)
Oded Goldreich, Dana Ron
Testing Distributions of Huge Objects. ITCS (2022)
Oded Goldreich, Tom Gur
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Theor. Comput. Sci. (2021)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Computational Complexity Conference (2021)
Oded Goldreich
Robust Self-Ordering versus Local Self-Ordering. Electron. Colloquium Comput. Complex. 28 (2021)
Marshall Ball, Oded Goldreich, Tal Malkin
Communication Complexity with Defective Randomness. Computational Complexity Conference (2021)
Oded Goldreich
Open Problems in Property Testing of Graphs. Electron. Colloquium Comput. Complex. 28 (2021)
Oded Goldreich, Dana Ron
A Lower Bound on the Complexity of Testing Grained Distributions. Electron. Colloquium Comput. Complex. 28 (2021)
Oded Goldreich
The KW Games as a Teaser. Electron. Colloquium Comput. Complex. 28 (2021)
Oded Goldreich
On the Locally Testable Code of Dinur et al. (2021). Electron. Colloquium Comput. Complex. 28 (2021)
Oded Goldreich, Dana Ron
Testing Distributions of Huge Objects. Electron. Colloquium Comput. Complex. 28 (2021)
Oded Goldreich, Avi Wigderson
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. FOCS (2021)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. CoRR (2021)
Oded Goldreich
On Testing Hamiltonicity in the Bounded Degree Graph Model. Electron. Colloquium Comput. Complex. 27 (2020)
Marshall Ball, Oded Goldreich, Tal Malkin
Communication Complexity with Defective Randomness. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich, Avi Wigderson
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich
On Counting $t$-Cliques Mod 2. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich, Avi Wigderson
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich
On Testing Asymmetry in the Bounded Degree Graph Model. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich, Dana Ron
The Subgraph Testing Model. ACM Trans. Comput. Theory 12 (4) (2020)
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 (2020)
Oded Goldreich, Dana Ron
One-Sided Error Testing of Monomials and Affine Subspaces. Electron. Colloquium Comput. Complex. 27 (2020)
Oded Goldreich
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model. CoRR (2019)
Oded Goldreich
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. Comput. Complex. 28 (4) (2019)
Oded Goldreich
On the Complexity of Estimating the Effective Support Size. Electron. Colloquium Comput. Complex. 26 (2019)
Oded Goldreich
Multi-pseudodeterministic algorithms. Electron. Colloquium Comput. Complex. 26 (2019)
Irit Dinur, Oded Goldreich, Tom Gur
Every Set in P Is Strongly Testable Under a Suitable Encoding. ITCS (2019)
Oded Goldreich, Tom Gur, Ilan Komargodski
Strong Locally Testable Codes with Relaxed Local Decoders. ACM Trans. Comput. Theory 11 (3) (2019)
Oded Goldreich, Dana Ron
The Subgraph Testing Model. ITCS (2019)
Marshall Ball, Oded Goldreich, Tal Malkin
Randomness Extraction from Somewhat Dependent Sources. Electron. Colloquium Comput. Complex. 26 (2019)
Oded Goldreich
Improved bounds on the AN-complexity of multilinear functions. Electron. Colloquium Comput. Complex. 26 (2019)
Itai Benjamini, Oded Goldreich
Pseudo-Mixing Time of Random Walks. Electron. Colloquium Comput. Complex. 26 (2019)
Oded Goldreich
Testing Isomorphism in the Bounded-Degree Graph Model. Electron. Colloquium Comput. Complex. 26 (2019)
Oded Goldreich
Testing graphs in vertex-distribution-free models. STOC (2019)
Oded Goldreich
Flexible models for testing graph properties. Electron. Colloquium Comput. Complex. 25 (2018)
Oded Goldreich
On Doubly-Efficient Interactive Proof Systems. Found. Trends Theor. Comput. Sci. 13 (3) (2018)
Oded Goldreich, Guy N. Rothblum
Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems. FOCS (2018)
Oded Goldreich, Avishay Tal
Matrix rigidity of random Toeplitz matrices. Comput. Complex. 27 (2) (2018)
Oded Goldreich, Tom Gur
Universal Locally Testable Codes. Chic. J. Theor. Comput. Sci. 2018 (2018)
Oded Goldreich, Guy N. Rothblum
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets. ITCS (2018)
Oded Goldreich, Tom Gur, Ron D. Rothblum
Proofs of proximity for context-free languages and read-once branching programs. Inf. Comput. 261 (2018)
Oded Goldreich, Guy N. Rothblum
Constant-round interactive proof systems for AC0[2] and NC1. Electron. Colloquium Comput. Complex. 25 (2018)
Oded Goldreich
Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. Electron. Colloquium Comput. Complex. 25 (2018)
Oded Goldreich, Guy N. Rothblum
-cliques: Worst-case to average-case reductions and Direct interactive proof systems. Electron. Colloquium Comput. Complex. 25 (2018)
Oded Goldreich, Dana Ron
The Subgraph Testing Model. Electron. Colloquium Comput. Complex. 25 (2018)
Irit Dinur, Oded Goldreich, Tom Gur
Every set in P is strongly testable under a suitable encoding. Electron. Colloquium Comput. Complex. 25 (2018)
Oded Goldreich
Testing Graphs in Vertex-Distribution-Free Models. Electron. Colloquium Comput. Complex. 25 (2018)
Oded Goldreich
Overview of the doubly-efficient interactive proof systems of RRR. Electron. Colloquium Comput. Complex. 24 (2017)
Oded Goldreich, Guy N. Rothblum
Simple doubly-efficient interactive proof systems for locally-characterizable sets. Electron. Colloquium Comput. Complex. 24 (2017)
Oded Goldreich, Avishay Tal
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Oded Goldreich
On the doubly-efficient interactive proof systems of GKR. Electron. Colloquium Comput. Complex. 24 (2017)
Oded Goldreich, Guy N. Rothblum
Worst-case to Average-case reductions for subclasses of P. Electron. Colloquium Comput. Complex. 24 (2017)
Oded Goldreich, Dana Ron
On Learning and Testing Dynamic Environments. J. ACM 64 (3) (2017)
Oded Goldreich
Deconstructing 1-local expanders. Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich, Igor Shinkar
Two-sided error proximity oblivious testing. Random Struct. Algorithms 48 (2) (2016)
Oded Goldreich, Tom Gur
Universal Locally Testable Codes. Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich, Maya Leshkowitz
On Emulating Interactive Proofs with Public Coins. Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich, Avishay Tal
Matrix rigidity of random toeplitz matrices. STOC (2016)
Oded Goldreich, Tom Gur
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP. Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich
Reducing testing affine spaces to testing linearity. Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich, Dana Ron
On Sample-Based Testers. ACM Trans. Comput. Theory 8 (2) (2016)
Oded Goldreich
The uniform distribution is complete with respect to testing identity to a fixed distribution. Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich
Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword. Comput. Complex. 25 (3) (2016)
Oded Goldreich, Dana Ron
On Sample-Based Testers. ITCS (2015)
Oded Goldreich, Tom Gur, Ron Rothblum
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs. Electron. Colloquium Comput. Complex. 22 (2015)
Oded Goldreich, Emanuele Viola, Avi Wigderson
On Randomness Extraction in AC0. Electron. Colloquium Comput. Complex. 22 (2015)
Oded Goldreich, Or Meir
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly. ACM Trans. Comput. Theory 7 (4) (2015)
Oded Goldreich, Tom Gur, Ilan Komargodski
Strong Locally Testable Codes with Relaxed Local Decoders. Computational Complexity Conference (2015)
Oded Goldreich, Avishay Tal
Matrix Rigidity of Random Toeplitz Matrices. Electron. Colloquium Comput. Complex. 22 (2015)
Oded Goldreich, Emanuele Viola, Avi Wigderson
On Randomness Extraction in AC0. Computational Complexity Conference (2015)
Oded Goldreich, Tom Gur, Ron D. Rothblum
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract). ICALP (1) (2015)
Oded Goldreich, Dana Ron
On Learning and Testing Dynamic Environments. FOCS (2014)
Oded Goldreich, Liav Teichner
Super-Perfect Zero-Knowledge Proofs. Electron. Colloquium Comput. Complex. 21 (2014)
Oded Goldreich, Avi Wigderson
On derandomizing algorithms that err extremely rarely. STOC (2014)
Oded Goldreich, Tom Gur, Ilan Komargodski
Strong Locally Testable Codes with Relaxed Local Decoders. Electron. Colloquium Comput. Complex. 21 (2014)
Oded Goldreich, Dana Ron
On Learning and Testing Dynamic Environments. Electron. Colloquium Comput. Complex. 21 (2014)
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
Finding cycles and trees in sublinear time. Random Struct. Algorithms 45 (2) (2014)
Oded Goldreich
On Multiple Input Problems in Property Testing. APPROX-RANDOM (2014)
Oded Goldreich
On Multiple Input Problems in Property Testing. Electron. Colloquium Comput. Complex. 20 (2013)

Oded Goldreich.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Oded Goldreich