# Studies in Complexity and Property Testing

## A collection of some unpublished works by Oded Goldreich

Given that the
collection of unpblished paper
compiled by me in 2010 (and appearing as
LNCS 6650 (in 2011))
seems to have been well-received,
I decided to publish another collection in 2020:
It appeared as
LNCS 12050,
with the following contents
[see tentative Preface and ToC].

- S. Decatur, O. Goldreich, and D. Ron,
A Probabilistic Error-Correcting Scheme
that Provides Partial Secrecy
- O. Goldreich and O. Meir,
Bridging a Small Gap
in the Gap Amplification of Assignment Testers
- O. Goldreich, On (Valiant's)
Polynomial-Size Monotone Formula for Majority
- O. Goldreich, Two Comments
on Targeted Canonical Derandomizers
- O. Goldreich, On the Effect of
the Proximity Parameter on Property Testers
- O. Goldreich and A. Wigderson,
On the Size of Depth-Three Boolean Circuits
for Computing Multilinear Functions
- O. Goldreich,
On the Communication Complexity Methodology
for Proving Lower Bounds on the Query Complexity of Property Testing
- O. Goldreich and L. Teichner,
Super-Perfect Zero-Knowledge Proofs
- O. Goldreich and D. Ron,
On the Relation between the Relative Earth Mover
Distance and the Variation Distance (an exposition)
- O. Goldreich,
The uniform distribution is complete
with respect to testing identity to a fixed distribution
- R. Tell,
A Note on Tolerant Testing with One-Sided Error
- O. Goldreich and M. Leshkowitz,
On Emulating Interactive Proofs with Public Coins
- O. Goldreich,
Reducing testing affine spaces
to testing linearity of functions
- O. Goldreich,
Deconstructing 1-local expanders
- O. Goldreich and G. Rothblum,
Worst-case to Average-case reductions
for subclasses of P
- O. Goldreich,
On the optimal analysis of the collision probability tester
(an exposition)
- O. Goldreich and A. Tal,
On Constant-Depth Canonical Boolean Circuits
for Computing Multilinear Functions
- O. Goldreich and G. Rothblum,
Constant-round interactive proof systems for AC0[2] and NC1
- O. Goldreich,
Flexible models for testing graph properties
- I. Benjamini and O. Goldreich,
Pseudo-Mixing Time of Random Walks
- O. Goldreich,
On constructing expanders for any number of vertices

**Warning:** The drafts posted above are not final versions,
and in some cases the final versions differ from them in significant ways.

©Copyright 2019 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.