A Small Gap in the Gap Amplification of Assignment Testers

Webpage for a note by Oded Goldreich and Or Meir

Abstract

An important extension of the proof of the PCP theorem by Irit Dinur (J. ACM 54(3), also ECCC TR05-046) is a gap amplification theorem for Assignment Testers. Specifically, this theorem states that the rejection probability of an Assignment Tester can be amplified by a constant factor, at the expense of increasing the output size of the Assignment Tester by a constant factor. We point out a gap in the proof of this theorem, and show that this gap can be filled.

Material available on-line

First version posted: Oct. 2007.
Revisions: none yet.

Back to either Oded Goldreich's homepage. or general list of papers.