Some Recent Papers by Oded Goldreich

last updated: Feb. 2011

The following papers can be obtained in Postscript

• L. Avigad and O. Goldreich, Testing Graph Blow-Up, March 2010.
• Z. Brakerski and O. Goldreich, From absolute distinguishability to positive distinguishability, March 2009.
• A. Czumaj, O. Goldreich, D. Ron, C. Seshadhri, A. Shapira, and C. Sohler, Finding Cycles and Trees in Sublinear Time, April 2010.
• O. Goldreich, A Candidate Counterexample to the Easy Cylinders Conjecture, March 2009.
• O. Goldreich, On Testing Computability by Small Width OBDDs, April 2010.
• O. Goldreich, In a World of P=BPP, August 2010.
• O. Goldreich, Two Comments on Targeted Canonical Derandomizers, April 2011.
• O. Goldreich, On the Effect of the Proximity Parameter on Property Testers, Feb. 2012.
• O. Goldreich and R. Izsak, Monotone Circuits: One-Way Functions versus Pseudorandom Generators, Sept 2011.
• O. Goldreich, B. Juba, and M. Sudan, A Theory of Goal-Oriented Communication, Sept 2009.
• O. Goldreich and T. Kaufman, Proximity Oblivious Testing and the Role of Invariances, April 2010.
• O. Goldreich, M. Krivelevich, I. Newman and E. Rozenberg, Hierarchy Theorems for Property Testing, Nov. 2008.
• O. Goldreich and O. Meir, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, Feb. 2011.
• O. Goldreich and D. Ron, Algorithmic Aspects of Property Testing in the Dense Graphs Model, April 2008.
• O. Goldreich and D. Ron, On Proximity Oblivious Testing, April 2008.