摘要：Dinurâs celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the expense of a fixed constant factor loss in the soundness gap). We note that the gap amplification can produce a Label Cover CSP. This allows us to reduce the alphabet size via a direct long-code based reduction from Label Cover to a Boolean CSP. Our composition step thus bypasses the concept of Assignment Testers from Dinurâs proof, and we believe it is more intuitive - it is just a gadget reduction. The analysis also uses only elementary facts (Parsevalâs identity) about Fourier Transforms over the hypercube.
关键词：PCP theorem; CSP; discrete Fourier analysis; label cover; long code
