Another Collection of Studies in Complexity and Property Testing
A collection of some unpublished works by Oded Goldreich
Following prior collections of unpblished papers of mine
compiled in 2010
and in 2020,
I'm compling another tentative collection.
It will be published as LNCS 15700
with the following preface.
- O. Goldreich, Multi-pseudodeterministic
algorithms, Jan. 2019.
[Rev: Jan 2025]
- O. Goldreich, On the Complexity of
Estimating the Effective Support Size, June 2019.
[Rev: Feb 2025]
- O. Goldreich, Testing Isomorphism
in the Bounded-Degree Graph Model, August 2019.
[Rev: Feb 2025]
- O. Goldreich and D. Ron, One-Sided Error
Testing of Monomials and Affine Subspaces, May 2020.
[Rev: Feb 2025]
- O. Goldreich,
On Counting $t$-Cliques Mod 2, July 2020.
[Rev: Nov 2024]
- O. Goldreich, On Testing Hamiltonicity
in the Bounded Degree Graph Model, July 2020.
[Rev: Feb 2025]
- O. Goldreich, On Testing Asymmetry
in the Bounded Degree Graph Model, August 2020.
[Rev: Feb 2025]
- O. Goldreich, Robust Self-Ordering
versus Local Self-Ordering, March 2021.
[Rev: Feb 2025]
- N. Bshouty and O. Goldreich,
On properties that are non-trivial to test,
Feb 2022.
[Rev: Apr 2024]
- O. Goldreich,
On the Locally Testable Codes of Dinur et al,
Nov 2021.
[Rev: Nov 2024]
- O. Goldreich and L. Tauber,
Testing in the bounded-degree graph model
with degree bound two, Dec 2022.
[Rev: Aug 2024]
- O. Goldreich, On the Lower Bound
on the Length of Relaxed Locally Decodable Codes, May 2023.
[Rev: Nov 2024]
- O. Goldreich, On the complexity
of enumerating ordered sets, Sept. 2023.
[Rev: Nov 2024]
- O. Goldreich and L. Tauber,
On Testing Isomorphism to a Fixed Graph
in the Bounded-Degree Graph Model, Sept 2023.
[Rev: Dec 2024]
- O. Goldreich,
On Parallel Repetitions
of Interactive Proof Systems, Sept 2023.
[Rev: Dec 2024]
- O. Goldreich, On coarse
and fine approximate counting of $t$-cliques, Sept. 2023.
[Rev: Dec 2024]
- O. Goldreich and L. Tauber,
On Testing Group Properties, Dec 2023.
[Rev: Dec 2024]
- O. Goldreich, On locally-characterized
expander graphs (a survey), Jan 2024.
[Rev: Dec 2024]
- O. Goldreich, On the query complexity of
testing local graph properties in the bounded-degree graph model,
Mar. 2024. [Rev: Dec 2024]
- O. Goldreich, On the relaxed LDC of BGHSV:
A survey that corrects the record, Apr 2024.
[Rev: Dec 2024]
- O. Goldreich, On the Cook-Mertz
Tree Evaluation procedure, June 2024.
[Rev: Dec 2024]
- O. Goldreich, Solving Tree Evaluation
in $o(\log n \cdot \log\log n)$ space, July 2024.
[Rev: Dec 2024]
- O. Goldreich,
On defining PPT-search problems, Oct. 2024.
[Rev: Jan 2025]
Warning: The drafts posted above are not final versions,
and in some cases the final versions differ from them in significant ways.
©Copyright 2024 by Oded Goldreich.
Permission to make copies of part or all of this work for personal
or classroom use is granted without fee provided that copies
are not made or distributed for profit or commercial
advantage and that new copies bear this notice and the full
citation on the first page. Abstracting with credit is permitted.
Back to Oded Goldreich's homepage.