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.