Some Recent Papers by Oded Goldreich
last updated: Jan 2025
The following papers can be obtained in Postscript or PDF
- N. Amir, O. Goldreich, and G. Rothblum.
Doubly Sub-linear Interactive Proofs of Proximity,
Sept 2024.
- N. Bshouty and O. Goldreich,
On properties that are non-trivial to test, Feb 2022.
- O. Goldreich, Robust Self-Ordering
versus Local Self-Ordering, March 2021.
- O. Goldreich, On the Lower Bound
on the Length of Relaxed Locally Decodable Codes, May 2023.
- O. Goldreich, On the complexity
of enumerating ordered sets, Sept. 2023.
- O. Goldreich, On coarse
and fine approximate counting of $t$-cliques, Sept. 2023.
- O. Goldreich, On the query complexity of
testing local graph properties in the bounded-degree graph model,
Mar. 2024.
- O. Goldreich, Solving Tree Evaluation
in $o(\log n \cdot \log\log n)$ space, July 2024.
- O. Goldreich,
On defining PPT-search problems, Oct. 2024.
- O. Goldreich and D. Ron, A Lower Bound
on the Complexity of Testing Grained Distributions, September 2021.
- O. Goldreich and D. Ron, Testing Distributions
of Huge Objects, September 2021.
- O. Goldreich, G. Rothblum, and T. Skverer,
On Interactive Proofs of Proximity
with Proof-Oblivious Queries, Sept 2022.
- O. Goldreich and L. Tauber,
Testing in the bounded-degree graph model
with degree bound two, Dec 2022.
- O. Goldreich and L. Tauber,
On Testing Isomorphism to a Fixed Graph
in the Bounded-Degree Graph Model, Sept 2023.
- O. Goldreich and L. Tauber,
On Testing Group Properties, Dec 2023.
- O. Goldreich and R. Tell,
Complexity theoretic implications
of pseudodeterministic algorithms for PPT-search problems, Feb 2025.
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers