Revisiting Alphabet Reduction in Dinur’s PCP

Guruswami, Venkatesan; Opršal, Jakub; Sandeep, Sai; Byrka, Jarosław; Meka, Raghu

doi:10.4230/lipics.approx/random.2020.34

Revisiting Alphabet Reduction in Dinur’s PCP

Guruswami, Venkatesan; Opršal, Jakub; Sandeep, Sai; Byrka, Jarosław; Meka, Raghu

Authors

Venkatesan Guruswami

Jakub Opršal

Sai Sandeep

Jarosław Byrka

Raghu Meka

Abstract

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.

Citation

Guruswami, V., Opršal, J., Sandeep, S., Byrka, J., & Meka, R. (2020). Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) (34:1-34:14). https://doi.org/10.4230/lipics.approx/random.2020.34

Conference Name	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Online Publication Date	Aug 11, 2020
Publication Date	2020
Deposit Date	Sep 14, 2020
Publicly Available Date	Sep 15, 2020
Pages	34:1-34:14
Series Title	Leibniz International Proceedings in Informatics (LIPIcs)
Series Number	176
Series ISSN	1868-8969
Book Title	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020).
DOI	https://doi.org/10.4230/lipics.approx/random.2020.34