Document Open Access Logo

Smooth and Strong PCPs

Author Orr Paradise

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.2.pdf
  • Filesize: 0.77 MB
  • 41 pages

Document Identifiers

Author Details

Orr Paradise
  • University of California, Berkeley, CA, USA

Acknowledgements

This work was done during my time at the Weizmann Institute of Science. It originated in a question of Irit Dinur, and I am grateful to her. My heartfelt appreciation goes to Oded Goldreich for guiding me through all stages of this work, from communication of Irit’s question to me and up to this very write-up. Many thanks to Madhu Sudan and Oded for providing the vector-valued low-degree test (Appendix C). I also thank Elad Granot and Roei Tell for the helpful discussions, and Amey Bhangale, Tom Gur, and Eylon Yogev for suggesting improvements to the write-up. I wish to thank an anonymous reviewer for pointing out an issue with the smoothness of the construction of Section 5.3 as it appeared in a previous version.

Cite AsGet BibTex

Orr Paradise. Smooth and Strong PCPs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 2:1-2:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.2

Abstract

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and incorrect claims are rejected with high probability (regardless of the given alleged proof). We consider two possible features of PCPs: - A PCP is strong if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof of that claim. - A PCP is smooth if each location in a proof is queried with equal probability. We prove that all sets in NP have PCPs that are both smooth and strong, are of polynomial length, and can be verified based on a constant number of queries. This is achieved by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), providing a stronger analysis of the Hadamard and Reed - Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in NP has a smooth strong canonical PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of NP witnesses to correct proofs. This improves on the recent construction of Dinur, Gur and Goldreich (ITCS, 2019) of PCPPs that are strong canonical but inherently non-smooth. Our result implies the hardness of approximating the satisfiability of "stable" 3CNF formulae with bounded variable occurrence, where stable means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric). This proves a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (SODA, 2019), suggesting a connection between the hardness of these instances and other stable optimization problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Interactive and probabilistic proof systems
  • Probabilistically checkable proofs
  • Hardness of approximation

Metrics

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

Related Versions

References

  1. Josh Alman and Lijie Chen. Efficient Construction of Rigid Matrices Using an NP Oracle. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, MD, USA, November 9-12, 2019, pages 1034-1055. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00067.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  3. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM, 45(1):70-122, 1998. URL: https://doi.org/10.1145/273865.273901.
  4. Pranjal Awasthi, Avrim Blum, and Or Sheffet. Stability Yields a PTAS for k-Median and k-Means Clustering. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 309-318. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.36.
  5. Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness of Approximation of Euclidean k-Means. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 754-767. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.SOCG.2015.754.
  6. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput., 36(4):889-974, 2006. URL: https://doi.org/10.1137/S0097539705446810.
  7. Yonatan Bilu and Nathan Linial. Lifts, Discrepancy and Nearly Optimal Spectral Gap*. Combinatorica, 26(5):495-519, 2006. URL: https://doi.org/10.1007/s00493-006-0029-7.
  8. Yonatan Bilu and Nathan Linial. Are Stable Instances Easy? Combinatorics, Probability & Computing, 21(5):643-660, 2012. URL: https://doi.org/10.1017/S0963548312000193.
  9. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. URL: https://doi.org/10.1016/0022-0000(93)90044-W.
  10. Irit Dinur, Oded Goldreich, and Tom Gur. Every Set in P Is Strongly Testable Under a Suitable Encoding. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 30:1-30:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.30.
  11. Irit Dinur and Omer Reingold. Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. SIAM J. Comput., 36(4):975-1024, 2006. URL: https://doi.org/10.1137/S0097539705446962.
  12. Zachary Friggstad, Kamyar Khodamoradi, and Mohammad R. Salavatipour. Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2958-2972. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.183.
  13. Anna Gál and Andrew Mills. Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length. TOCT, 3(2):5:1-5:34, 2012. URL: https://doi.org/10.1145/2077336.2077338.
  14. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  15. Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong Locally Testable Codes with Relaxed Local Decoders. TOCT, 11(3):17:1-17:38, 2019. URL: https://doi.org/10.1145/3319907.
  16. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, and Luca Trevisan. Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity, 15(3):263-296, 2006. URL: https://doi.org/10.1007/s00037-006-0216-3.
  17. Oded Goldreich and Madhu Sudan. Locally testable codes and PCPs of almost-linear length. J. ACM, 53(4):558-655, 2006. URL: https://doi.org/10.1145/1162349.1162351.
  18. Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed Locally Correctable Codes. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 27:1-27:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.27.
  19. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Computational Complexity, 27(1):99-207, 2018. URL: https://doi.org/10.1007/s00037-016-0136-9.
  20. Prahladh Harsha. Robust PCPs of Proximity and Shorter PCPs. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2004. Google Scholar
  21. Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 80-86. ACM, 2000. URL: https://doi.org/10.1145/335305.335315.
  22. Subhash Khot. Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 23-32. IEEE Computer Society, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181879.
  23. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences, 43(3):425-440, 1991. URL: https://doi.org/10.1016/0022-0000(91)90023-X.
  24. Sergey Yekhanin. Locally Decodable Codes. Foundations and Trends in Theoretical Computer Science, 6(3):139-255, 2012. URL: https://doi.org/10.1561/0400000030.
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact