Cube vs. Cube Low Degree Test

Authors Amey Bhangale, Irit Dinur, Inbal Livni Navon



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.40.pdf
  • Filesize: 0.57 MB
  • 31 pages

Document Identifiers

Author Details

Amey Bhangale
Irit Dinur
Inbal Livni Navon

Cite AsGet BibTex

Amey Bhangale, Irit Dinur, and Inbal Livni Navon. Cube vs. Cube Low Degree Test. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 40:1-40:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ITCS.2017.40

Abstract

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension 3) that intersect on a point x in F^m, and checks that the assignments to the cubes agree with each other on the point x. Our main result is a new combinatorial proof for a low degree test that comes closer to the soundness limit, as it works for all epsilon >= poly(d)/{|F|}^{1/2}, where d is the degree. This should be compared to the previously best soundness value of epsilon >= poly(m, d)/|F|^{1/8}. Our soundness limit improves upon the dependence on the field size and does not depend on the dimension of the ambient space. Our proof is combinatorial and direct: unlike the Raz-Safra proof, it proceeds in one shot and does not require induction on the dimension of the ambient space. The ideas in our proof come from works on direct product testing which are even simpler in the current setting thanks to the low degree. Along the way we also prove a somewhat surprising fact about connection between different agreement tests: it does not matter if the tester chooses the cubes to intersect on points or on lines: for every given table, its success probability in either test is nearly the same.
Keywords
  • Low Degree Test
  • Probabilistically Checkable Proofs
  • Locally Testable Codes

Metrics

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

References

  1. Sanjeev Arora and Madhu Sudan. Improved low-degree testing and its applications. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 485-495. ACM, 1997. Google Scholar
  2. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs, and nonapproximability - towards tight results. SIAM Journal on Computing, 27(3):804-915, June 1998. Google Scholar
  3. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 73-83, 1990. Google Scholar
  4. A.E. Brouwer, A.M. Cohen, and A. Neumaier. Distance-regular graphs. Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer, 1989. Google Scholar
  5. Irit Dinur and Elazar Goldenberg. Locally testing direct product in the low error range. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 613-622. IEEE, 2008. Google Scholar
  6. Irit Dinur and Omer Reingold. Assignment testers: Towards combinatorial proofs of the PCP theorem. SIAM Journal on Computing, 36(4):975-1024, 2006. Special issue on Randomness and Computation. Google Scholar
  7. Irit Dinur and David Steurer. Direct product testing. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 188-196. IEEE, 2014. Google Scholar
  8. Oded Goldreich and Shmuel Safra. A combinatorial consistency lemma with application to proving the PCP theorem. In RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science. LNCS, 1997. Google Scholar
  9. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. New direct-product testers and 2-query PCPs. SIAM Journal on Computing, 41(6):1722-1768, 2012. Google Scholar
  10. Dana Moshkovitz and Ran Raz. Sub-constant error low degree test of almost-linear size. SIAM J. Computing, 38(1):140-180, 2008. Google Scholar
  11. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 475-484. ACM, 1997. Google Scholar
  12. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  13. van der Waerden, E. Artin, E. Noether, and F. Blum. Modern Algebra, volume 1. Frederick Ungar Publishing, 1949. 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