Document Open Access Logo

Revisiting Alphabet Reduction in Dinur’s PCP

Authors Venkatesan Guruswami , Jakub Opršal , Sai Sandeep

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2020.34.pdf
  • Filesize: 486 kB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Approximation algorithms analysis
Keywords
  • PCP theorem
  • CSP
  • discrete Fourier analysis
  • label cover
  • long code

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.34

Author Details

Venkatesan Guruswami
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Jakub Opršal
  • Computer Science Department, Durham University, UK
Sai Sandeep
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Guruswami, Venkatesan: Supported in part by NSF grants CCF-1526092, CCF-1814603, and CCF-1908125.
  • Opršal, Jakub: Received funding from the UK EPSRC grant EP/R034516/1. Most of the work has been done during a visit to Carnegie Mellon University.
  • Sandeep, Sai: Supported in part by NSF grant CCF-1908125.

Acknowledgements

We would like to thank Irit Dinur, Margalit Glasgow, Oded Goldreich, Prahladh Harsha, Johan Håstad, Jaikumar Radhakrishnan, and Madhu Sudan for useful comments and feedback. We also thank the anonymous reviewers for valuable comments on the presentation.

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  2. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. URL: https://doi.org/10.1145/273865.273901.
  3. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-Sat is NP-hard. SIAM J. Comput., 46(5):1554-1573, 2017. URL: https://doi.org/10.1137/15M1006507.
  4. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  5. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability-towards tight results. SIAM J. Comput., 27(3):804-915, 1998. URL: https://doi.org/10.1137/S0097539796302531.
  6. Jakub Bulín, Andrei Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing (STOC ’19), New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3313276.3316300.
  7. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12, 2007. URL: https://doi.org/10.1145/1236457.1236459.
  8. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput., 36(4):975-1024, 2006. Google Scholar
  9. Ehud Friedgut, Gil Kalai, and Assaf Naor. Boolean functions whose Fourier transform is concentrated on the first two levels. Adv. in Applied Math., 29:427-437, 2002. Google Scholar
  10. Venkatesan Guruswami and Ryan O'Donnell. The PCP theorem and hardness of approximation: Notes on lectures 7-9. https://courses.cs.washington.edu/courses/cse533/05au/, 2005.
  11. Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. URL: https://doi.org/10.1145/502090.502098.
  12. Jaikumar Radhakrishnan and Madhu Sudan. On Dinur’s proof of the PCP theorem. Bull. Amer. Math. Soc., 44:19-61, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact