TR19-092 Authors: Venkatesan Guruswami, Jakub OprÅ¡al, Sai Sandeep

Publication: 9th July 2019 19:04

Downloads: 265

Keywords:

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.