Document Open Access Logo

Every Set in P Is Strongly Testable Under a Suitable Encoding

Authors Irit Dinur, Oded Goldreich, Tom Gur

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.30.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Irit Dinur
  • Weizmann Institute, Rehovot, Israel
Oded Goldreich
  • Weizmann Institute, Rehovot, Israel
Tom Gur
  • University of Warwick, UK

Funding

  • Dinur, Irit: Supported by ERC-CoG grant 772839. Weizmann Institute of Science.
  • Goldreich, Oded: Supported by the Israel Science Foundation (grants No. 671/13 and 1146/18).
  • Gur, Tom: Supported in part by the UC Berkeley Center for Long-Term Cybersecurity.

Cite As Get BibTex

Irit Dinur, Oded Goldreich, and Tom Gur. Every Set in P Is Strongly Testable Under a Suitable Encoding. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.30

Abstract

We show that every set in P is strongly testable under a suitable encoding. By "strongly testable" we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By a "suitable encoding" we mean one that is polynomial-time computable and invertible. This result stands in contrast to the known fact that some sets in P are extremely hard to test, providing another demonstration of the crucial role of representation in the context of property testing.
The testing result is proved by showing that any set in P has a strong canonical PCP, where canonical means that (for yes-instances) there exists a single proof that is accepted with probability 1 by the system, whereas all other potential proofs are rejected with probability proportional to their distance from this proof. In fact, we show that UP equals the class of sets having strong canonical PCPs (of logarithmic randomness), whereas the class of sets having strong canonical PCPs with polynomial proof length equals "unambiguous- MA". Actually, for the testing result, we use a PCP-of-Proximity version of the foregoing notion and an analogous positive result (i.e., strong canonical PCPPs of logarithmic randomness for any set in UP).

Subject Classification

ACM Subject Classification
  • Theory of computation → Probabilistic computation
Keywords
  • Probabilistically checkable proofs
  • property testing

Metrics

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

Related Versions

References

  1. N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy. Efficient testing of large graphs. Combinatorica, 20:451-476, 2000. Google Scholar
  2. N. Alon, E. Fischer, I. Newman, and A. Shapira. A combinatorial characterization of the testable graph properties: It’s all about regularity. STOC, pages 251-260, 2006. Google Scholar
  3. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. JACM, 45:501-555, 1998. Google Scholar
  4. S. Arora and S. Safra. Probabilistic checkable proofs: A new characterization of NP. JACM, 45:70-122, 1998. Google Scholar
  5. E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan. Robust pcps of proximity, shorter pcps, and applications to coding. SICOMP, 36(4):889-974, 2006. Google Scholar
  6. E. Ben-Sasson and M. Sudan. Short pcps with polylog query complexity. SICOMP, 38(2):551-607, 2008. Google Scholar
  7. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. JCSS, 47(3):549-595, 1993. Google Scholar
  8. I. Dinur. The pcp theorem by gap amplification. JACM, 54:3, 2007. Google Scholar
  9. I. Dinur, O. Goldreich, and T. Gur. Every set in p is strongly testable under a suitable encoding. Technical report, in ECCC TR18-050, 2018. Google Scholar
  10. I. Dinur and O. Reingold. Assignment-testers: Towards a combinatorial proof of the pcp-theorem. FOCS, 45, 2004. Google Scholar
  11. O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. Google Scholar
  12. O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  13. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. JACM, pages 653-750, 1998. Google Scholar
  14. O. Goldreich, T. Gur, and I. Komargodski. Strong locally testable codes with relaxed local decoders. CCC, 30:1-41, 2015. Google Scholar
  15. O. Goldreich, M. Krivelevich, I. Newman, and E. Rozenberg. Hierarchy theorems for property testing. Computational Complexity, 21(1):129-192, 2012. Google Scholar
  16. O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, pages 302-343, 2002. Google Scholar
  17. O. Goldreich and D. Ron. On proximity oblivious testing. SICOMP, 40(2):534-566, 2011. Google Scholar
  18. O. Goldreich and I. Shinkar. Two-sided error proximity oblivious testing. RSA, 48(2):341-383, 2016. Google Scholar
  19. O. Goldreich and M. Sudan. Locally testable codes and pcps of almost-linear length. JACM, 53(4):558-655, 2006. Google Scholar
  20. T. Gur, G. Ramnarayan, and R. Rothblum. Relaxed Locally Correctable Codes. ITCS. ECCC, 2018. Google Scholar
  21. T. Gur and R. Rothblum. Non-interactive proofs of proximity. Computational Complexity, 2018. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact