ECCC-Report TR19-092https://eccc.weizmann.ac.il/report/2019/092Comments and Revisions published for TR19-092en-usTue, 09 Jul 2019 19:04:11 +0300
Paper TR19-092
| Revisiting Alphabet Reduction in Dinur's PCP |
Venkatesan Guruswami,
Jakub OprÅ¡al,
Sai Sandeep
https://eccc.weizmann.ac.il/report/2019/092Dinur'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. Tue, 09 Jul 2019 19:04:11 +0300https://eccc.weizmann.ac.il/report/2019/092