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.