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 compiled another collection, which will be published (in June 2025) as LNCS 15700. Here is the preface and the list of papers.

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.