Exponentially Small Soundness for the Direct Product Z-Test

Authors Irit Dinur, Inbal Livni Navon



PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.29.pdf
  • Filesize: 0.76 MB
  • 50 pages

Document Identifiers

Author Details

Irit Dinur
Inbal Livni Navon

Cite AsGet BibTex

Irit Dinur and Inbal Livni Navon. Exponentially Small Soundness for the Direct Product Z-Test. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 29:1-29:50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CCC.2017.29

Abstract

Given a function f:[N]^k->[M]^k, the Z-test is a three query test for checking if a function f is a direct product, namely if there are functions g_1,...g_k:[N]->[M] such that f(x_1,...,x_k)=(g_1(x_1),...,g_k(x_k)) for every input x in [N]^k. This test was introduced by Impagliazzo et. al. (SICOMP 2012), who showed that if the test passes with probability epsilon > exp(-sqrt k) then f is Omega(epsilon) close to a direct product function in some precise sense. It remained an open question whether the soundness of this test can be pushed all the way down to exp(-k) (which would be optimal). This is our main result: we show that whenever f passes the Z test with probability epsilon > exp(-k), there must be a global reason for this: namely, f must be close to a product function on some Omega(epsilon) fraction of its domain. Towards proving our result we analyze the related (two-query) V-test, and prove a "restricted global structure" theorem for it. Such theorems were also proven in previous works on direct product testing in the small soundness regime. The most recent work, by Dinur and Steurer (CCC 2014), analyzed the V test in the exponentially small soundness regime. We strengthen their conclusion of that theorem by moving from an "in expectation" statement to a stronger "concentration of measure" type of statement, which we prove using hyper-contractivity. This stronger statement allows us to proceed to analyze the Z test. We analyze two variants of direct product tests. One for functions on ordered tuples, as above, and another for functions on sets of size k. The work of Impagliazzo et al. was actually focused only on functions of the latter type, i.e. on sets. We prove exponentially small soundness for the Z-test for both variants. Although the two appear very similar, the analysis for tuples is more tricky and requires some additional ideas.
Keywords
  • Direct Product Testing
  • Property Testing
  • Agreement

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. Vitaly Bergelson, Terence Tao, and Tamar Ziegler. An inverse theorem for the uniformity seminorms associated with the action of 𝔽^∞_p. Geometric and Functional Analysis, 19(6):1539-1596, 2010. Google Scholar
  3. Amey Bhangale, Irit Dinur, and Inbal Livni Navon. Cube vs. cube low degree test. In Proceedings of the 2017 Conference on Innovations in Theoretical Computer Science, ITCS, 2017. Google Scholar
  4. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54(3):12, 2007. 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, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? Electronic Colloquium on Computational Complexity (ECCC), 2016. URL: https://eccc.weizmann.ac.il/report/2016/198/.
  7. Irit Dinur and David Steurer. Direct product testing. In Computational Complexity (CCC), 2014 IEEE 29th Conference on, pages 188-196. IEEE, 2014. Google Scholar
  8. Oded Goldreich and Shmuel Safra. A combinatorial consistency lemma with application to proving the PCP theorem. SIAM Journal on Computing, 29(4):1132-1154, 2000. 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. Subhash Khot, Dor Minzer, and Muli Safra. On Independent Sets, 2-to-2 Games and Grassmann Graphs. Electronic Colloquium on Computational Complexity (ECCC), 2016. Google Scholar
  11. Elchanan Mossel, Krzysztof Oleszkiewicz, and Arnab Sen. On reverse hypercontractivity. Geometric and Functional Analysis, 23(3):1062-1097, 2013. Google Scholar
  12. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. Google Scholar
  13. 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
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