Skip to main content

Research Repository

Advanced Search

Revisiting Alphabet Reduction in Dinur’s PCP

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

Revisiting Alphabet Reduction in Dinur’s PCP Thumbnail


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

Files





You might also like



Downloadable Citations