Some Recent Papers by Oded Goldreich
last updated: Dec. 2022
The following papers can be obtained in Postscript or PDF
- M. Ball, O. Goldreich, and T. Malkin, Randomness
Extraction from Somewhat Dependent Sources, Dec 2019.
- M. Ball, O. Goldreich, and T. Malkin, Communication
Complexity with Defective Randomness, April 2020.
- N. Bshouty and O. Goldreich,
On properties that are non-trivial to test, Feb 2022.
- I. Benjamini and O. Goldreich,
Pseudo-Mixing Time of Random Walks June 2019.
- I. Dinur, O. Goldreich, and T. Gur, Every set
in P is strongly testable under a suitable encoding, Mar 2018.
- O. Goldreich, On the doubly-efficient
interactive proof systems of GKR, June 2017.
- O. Goldreich, Overview of the doubly-efficient
interactive proof systems of RRR, June 2017.
- O. Goldreich, Hierarchy Theorems
for Testing Properties in Size-Oblivious Query Complexity, May 2018.
- O. Goldreich, Flexible models
for testing graph properties, May 2018.
- O. Goldreich, Testing Graphs
in Vertex-Distribution-Free Models , Oct. 2018.
- O. Goldreich, Multi-pseudodeterministic
algorithms, Jan. 2019.
- O. Goldreich, Testing Bipartitness
in an Augmented VDF Bounded-Degree Graph Model, May 2019.
- O. Goldreich, On the Complexity of
Estimating the Effective Support Size, June 2019.
- O. Goldreich, Testing Isomorphism
in the Bounded-Degree Graph Model, August 2019.
- O. Goldreich, Improved bounds on
the AN-complexity of multilinear functions, Nov. 2019.
- O. Goldreich,
On Counting $t$-Cliques Mod 2, July 2020.
- O. Goldreich, On Testing Hamiltonicity
in the Bounded Degree Graph Model, July 2020.
- O. Goldreich, On Testing Asymmetry
in the Bounded Degree Graph Model, August 2020.
- 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 and D. Ron,
The Subgraph Testing Model, Mar. 2018.
- O. Goldreich and D. Ron, One-Sided Error
Testing of Monomials and Affine Subspaces, May 2020.
- 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 and G. Rothblum,
Simple doubly-efficient interactive proof systems
for locally-characterizable sets , Feb. 2017.
- O. Goldreich and G. Rothblum,
Worst-case to Average-case reductions
for subclasses of P, Aug. 2017.
- O. Goldreich and G. Rothblum,
Counting $t$-cliques: Worst-case to average-case
reductions and Direct interactive proof systems, Mar. 2018.
- O. Goldreich and G. Rothblum,
Constant-round interactive proof systems
for AC0[2] and NC1, Apr. 2018.
- O. Goldreich, G. Rothblum, and T. Skverer,
On Interactive Proofs of Proximity
with Proof-Oblivious Queries, Sept 2022.
- O. Goldreich and A. Tal, On Constant-Depth
Canonical Boolean Circuits for Computing Multilinear Functions, Dec 2017.
- O. Goldreich and L. Tauber,
Testing in the bounded-degree graph model
with degree bound two, Dec 2022.
- O. Goldreich and A. Wigderson,
Robustly Self-Ordered Graphs:
Constructions and Applications to Property Testing, Sept 2020.
- O. Goldreich and A. Wigderson,
Non-adaptive vs Adaptive Queries
in the Dense Graph Testing Model, Nov 2020.
- O. Goldreich and A. Wigderson, Constructing
Large Families of Pairwise Far Permutations: Good
Permutation Codes Based on the Shuffle-Exchange Network, Dec 2020.
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers