Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-092 | 9th July 2019 19:03

Revisiting Alphabet Reduction in Dinur's PCP


Authors: Venkatesan Guruswami, Jakub Opršal, Sai Sandeep
Publication: 9th July 2019 19:04
Downloads: 1159


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.

ISSN 1433-8092 | Imprint