Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.34
URN: urn:nbn:de:0030-drops-126372
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12637/
Guruswami, Venkatesan ; Opršal, Jakub ; Sandeep, Sai
Revisiting Alphabet Reduction in Dinur’s PCP
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{guruswami_et_al:LIPIcs:2020:12637,
author = {Venkatesan Guruswami and Jakub Opr{\v{s}}al and Sai Sandeep},
title = {{Revisiting Alphabet Reduction in Dinur’s PCP}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {34:1--34:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12637},
URN = {urn:nbn:de:0030-drops-126372},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.34},
annote = {Keywords: PCP theorem, CSP, discrete Fourier analysis, label cover, long code}
}
| Keywords: | PCP theorem, CSP, discrete Fourier analysis, label cover, long code | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 11.08.2020 |
