Document Open Access Logo

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

Authors Amit Levi, Erik Waingarten

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.52.pdf
  • Filesize: 0.62 MB
  • 20 pages

Document Identifiers

Author Details

Amit Levi
  • University of Waterloo, Canada
Erik Waingarten
  • Columbia University, USA

Funding

  • Levi, Amit: Research supported by NSERC Discovery grant and the David R. Cheriton Graduate Scholarship. Part of this work was done while the author was visiting Columbia University.
  • Waingarten, Erik: This work is supported in part by the NSF Graduate Research Fellowship under Grant No. DGE-16-44869, CCF-1703925, CCF-1563155, and CCF-1420349.

Cite AsGet BibTex

Amit Levi and Erik Waingarten. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.52

Abstract

We introduce a new model for testing graph properties which we call the rejection sampling model. We show that testing bipartiteness of n-nodes graphs using rejection sampling queries requires complexity Omega~(n^2). Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions of the form f : {0,1}^n -> {0,1}: - Tolerant k-junta testing with non-adaptive queries requires Omega~(k^2) queries. - Tolerant unateness testing requires Omega~(n) queries. - Tolerant unateness testing with non-adaptive queries requires Omega~(n^{3/2}) queries. Given the O~(k^{3/2})-query non-adaptive junta tester of Blais [Eric Blais, 2008], we conclude that non-adaptive tolerant junta testing requires more queries than non-tolerant junta testing. In addition, given the O~(n^{3/4})-query unateness tester of Chen, Waingarten, and Xie [Xi Chen et al., 2017] and the O~(n)-query non-adaptive unateness tester of Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri [Roksana Baleshzar et al., 2017], we conclude that tolerant unateness testing requires more queries than non-tolerant unateness testing, in both adaptive and non-adaptive settings. These lower bounds provide the first separation between tolerant and non-tolerant testing for a natural property of Boolean functions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Probabilistic computation
Keywords
  • Property Testing
  • Juntas
  • Tolerant Testing
  • Boolean functions

Metrics

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

Related Versions

References

  1. Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu. Estimating the distance to a monotone function. Random Structures and Algorithms, 31(3):371-383, 2007. Google Scholar
  2. Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. A lower bound for nonadaptive, one-sided error testing of unateness of Boolean functions over the hypercube. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.00053.
  3. Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal Unateness Testers for Real-Values Functions: Adaptivity Helps. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP '2017), 2017. Google Scholar
  4. Aleksandrs Belovs and Eric Blais. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th ACM Symposium on the Theory of Computing (STOC '2016), pages 1021-1032, 2016. Google Scholar
  5. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Tolerant Testers of Image Properties. In Proceedings of the 43th International Colloquium on Automata, Languages and Programming (ICALP '2016), pages 90:1-90:14, 2016. Google Scholar
  6. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC '2014), 2014. Google Scholar
  7. Eric Blais. Improved bounds for testing juntas. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 317-330. Springer, 2008. Google Scholar
  8. Eric Blais. Testing juntas nearly optimally. In Proceedings of the 41st ACM Symposium on the Theory of Computing (STOC '2009), pages 151-158, 2009. Google Scholar
  9. Eric Blais, Clément L Canonne, Talya Eden, Amit Levi, and Dana Ron. Tolerant junta testing and the connection to submodular optimization and function isomorphism. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA '2018), pages 2113-2132, 2018. Google Scholar
  10. Harry Buhrman, David Garcıa-Soriano, Arie Matsliah, and Ronald de Wolf. The non-adaptive query complexity of testing k-parities. Chicago Journal of Theoretical Computer Science, 6:1-11, 2013. Google Scholar
  11. Andrea Campagna, Alan Guo, and Ronitt Rubinfeld. Local reconstructors and tolerant testers for connectivity and diameter. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 411-424. Springer, 2013. Google Scholar
  12. Clément L. Canonne, Dana Ron, and Rocco A. Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing, 44(3):540-616, 2015. Google Scholar
  13. Deeparnab Chakrabarty and Seshadhri Comandur. An o(n) monotonicity tester for boolean functions over the hypercube. SIAM Journal on Computing, 45(2):461-472, 2016. Google Scholar
  14. Deeparnab Chakrabarty and C. Seshadhri. A Õ(n) non-adaptive tester for unateness. arXiv preprint, 2016. URL: http://arxiv.org/abs/1608.06980.
  15. Sourav Chakraborty, Eldar Fischer, David García-Soriano, and Arie Matsliah. Junto-symmetric functions, hypergraph isomorphism and crunching. In Proceedings of the 27th Conference on Computational Complexity (CCC '2012), pages 148-158. IEEE, 2012. Google Scholar
  16. Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah. On the power of conditional samples in distribution testing. SIAM Journal on Computing, 45(4):1261-1296, 2016. Google Scholar
  17. Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. In Proceedings of the 32nd Conference on Computational Complexity (CCC '2017), 2017. Google Scholar
  18. Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. In Proceedings of the 49th ACM Symposium on the Theory of Computing (STOC '2017), 2017. Google Scholar
  19. Xi Chen, Erik Waingarten, and Jinyu Xie. Boolean Unateness Testing with Õ(n^3/4) Adaptive Queries. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS '2017), 2017. Google Scholar
  20. Hana Chockler and Dan Gutfreund. A lower bound for testing juntas. Information Processing Letters, pages 301-305, 2004. Google Scholar
  21. Ilias Diakonikolas, Homin K Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A Servedio, and Andrew Wan. Testing for concise representations. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS '2007), pages 549-558. IEEE, 2007. Google Scholar
  22. Shahar Fattal and Dana Ron. Approximating the distance to monotonicity in high dimensions. ACM Transactions on Algorithms, 6(3):52, 2010. Google Scholar
  23. Eldar Fischer and Lance Fortnow. Tolerant versus intolerant testing for Boolean properties. Theory of Computing, 2(9):173-183, 2006. Google Scholar
  24. Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences, 68(4):753-787, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.11.004.
  25. Eldar Fischer and Ilan Newman. Testing versus estimation of graph properties. SIAM Journal on Computing, 37(2):482-501, 2007. Google Scholar
  26. Oded Goldreich. Introduction to property testing. Cambridge University Press, 2017. Google Scholar
  27. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samordinsky. Testing Monotonicity. Combinatorica, 20(3):301-337, 2000. Google Scholar
  28. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, 1998. Google Scholar
  29. Oded Goldreich and Dana Ron. On sample-based testers. ACM Transactions on Computation Theory, 8(2), 2016. Google Scholar
  30. Venkatesan Guruswami and Atri Rudra. Tolerant locally testable codes. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 306-317. Springer, 2005. Google Scholar
  31. Subhash Khot and Igor Shinkar. An Õ(n) queries adaptive tester for unateness. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 37:1-37:7, 2016. Google Scholar
  32. Swastik Kopparty and Shubhangi Saraf. Tolerant linearity testing and locally testable codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 601-614. Springer, 2009. Google Scholar
  33. Sharon Marko and Dana Ron. Approximating the distance to properties in bounded-degree and general sparse graphs. ACM Transactions on Algorithms, 5(2):22, 2009. Google Scholar
  34. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012-1042, 2006. Google Scholar
  35. Dana Ron. Property testing: A learning theory perspective. Foundations and Trendsregistered in Machine Learning, 1(3):307-402, 2008. Google Scholar
  36. Dana Ron. Algorithmic and analysis techniques in property testing. Foundations and Trendsregistered in Theoretical Computer Science, 5(2):73-205, 2010. Google Scholar
  37. Rocco A Servedio, Li-Yang Tan, and John Wright. Adaptivity helps for testing juntas. In Proceedings of the 30th Conference on Computational Complexity (CCC '2015), pages 264-279, 2015. Google Scholar
  38. Roei Tell. A Note on Tolerant Testing with One-Sided Error. In Electronic Colloquium on Computational Complexity (ECCC), volume 23, page 32, 2016. 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 Imprint Privacy Contact