Venkatesan Guruswami
Revisiting Alphabet Reduction in Dinur’s PCP
Guruswami, Venkatesan; Opršal, Jakub; Sandeep, Sai; Byrka, Jarosław; Meka, Raghu
Authors
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, December). Revisiting Alphabet Reduction in Dinur’s PCP. Presented at Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Presentation Conference Type | Conference Paper (published) |
---|---|
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 |
Public URL | https://durham-repository.worktribe.com/output/1141983 |
Files
Published Conference Proceeding
(498 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep; licensed under Creative Commons License CC-BY.
You might also like
Deciding the Existence of Minority Terms
(2019)
Journal Article
Algebraic Approach to Promise Constraint Satisfaction
(2021)
Journal Article
ω-categorical structures avoiding height 1 identities
(2020)
Journal Article
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
(2019)
Presentation / Conference Contribution
Algebraic approach to promise constraint satisfaction
(2019)
Presentation / Conference Contribution