Document Open Access Logo

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

Authors Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.5.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Roksana Baleshzar
Deeparnab Chakrabarty
Ramesh Krishnan S. Pallavoor
Sofya Raskhodnikova
C. Seshadhri

Cite As Get BibTex

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.5

Abstract

We study the problem of testing unateness of functions f:{0,1}^d -> R. We give an O(d/\epsilon . log(d/\epsilon))-query nonadaptive tester and an O(d/\epsilon)-query adaptive tester and show that both testers are optimal for a fixed distance parameter \epsilon. Previously known unateness testers worked only for Boolean functions, and their query complexity had worse dependence on the dimension both for the adaptive and the nonadaptive case. Moreover, no lower bounds for testing unateness were known. We generalize our results to obtain optimal unateness testers for functions f:[n]^d -> R.

Our results establish that adaptivity helps with testing unateness of real-valued functions on domains of the form {0,1}^d and, more generally, [n]^d. This stands in contrast to the situation for monotonicity testing where there is no adaptivity gap for functions f:[n]^d -> R.

Subject Classification

Keywords
  • Property testing
  • unate and monotone functions

Metrics

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

References

  1. Nir Ailon and Bernard Chazelle. Information theory in property testing and monotonicity testing in higher dimension. Inf. Comput., 204(11):1704-1717, 2006. Google Scholar
  2. Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal unateness testers for real-valued functions: Adaptivity helps. Electronic Colloquium on Computational Complexity (ECCC), 2017, 2017. Also appeared as arXiv report 1703.05199 (https://arxiv.org/abs/1703.05199). URL: https://eccc.weizmann.ac.il/report/2017/049/.
  3. Tugkan Batu, Ronitt Rubinfeld, and Patrick White. Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput., 196(1):42-56, 2005. Google Scholar
  4. Aleksandrs Belovs and Eric Blais. Quantum algorithm for monotonicity testing on the hypercube. Theory of Computing, 11:403-412, 2015. Google Scholar
  5. Aleksandrs Belovs and Eric Blais. A polynomial lower bound for testing monotonicity. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 1021-1032, 2016. Google Scholar
  6. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 164-173, 2014. Google Scholar
  7. Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff. Transitive-closure spanners. SIAM J. Comput., 41(6):1380-1425, 2012. Google Scholar
  8. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. Google Scholar
  9. Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In Proceedings, IEEE Conference on Computational Complexity (CCC), pages 309-320, 2014. Google Scholar
  10. Jop Briët, Sourav Chakraborty, David García-Soriano, and Arie Matsliah. Monotonicity testing and shortest-path routing on the cube. Combinatorica, 32(1):35-53, 2012. Google Scholar
  11. Deeparnab Chakrabarty. Monotonicity testing. In Encyclopedia of Algorithms, pages 1352-1356. Springer, 2016. Google Scholar
  12. Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri. Property testing on product distributions: Optimal testers for bounded derivative properties. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1809-1828, 2015. Google Scholar
  13. Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 419-428, 2013. Google Scholar
  14. Deeparnab Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing, 10:453-464, 2014. Google Scholar
  15. Deeparnab Chakrabarty and C. Seshadhri. An o(n) monotonicity tester for boolean functions over the hypercube. SIAM J. Comput., 45(2):461-472, 2016. Google Scholar
  16. Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity testing requires (almost) O(n^1/2) non-adaptive queries. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 519-528, 2015. Google Scholar
  17. Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 286-295, 2014. Google Scholar
  18. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin M. Varma. Erasure-resilient property testing. In Proceedings, International Colloquium on Automata, Languages and Processing (ICALP), pages 91:1-91:15, 2016. Google Scholar
  19. Yevgeny Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. Proceedings, International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 97-108, 1999. Google Scholar
  20. Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan. Spot-checkers. J. Comput. System Sci., 60(3):717-751, 2000. Google Scholar
  21. Eldar Fischer. On the strength of comparisons in property testing. Inf. Comput., 189(1):107-116, 2004. Google Scholar
  22. Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 474-483, 2002. Google Scholar
  23. Oded Goldreich. Introduction to property testing (working draft), 2015. URL: http://www.wisdom.weizmann.ac.il/~oded/PDF/pt-v1.pdf.
  24. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Combinatorica, 20:301-337, 2000. Google Scholar
  25. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. Google Scholar
  26. Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. SIAM J. Comput., 37(4):1107-1138, 2007. Google Scholar
  27. Shirley Halevy and Eyal Kushilevitz. Testing monotonicity over graph products. Random Struct. Algorithms, 33(1):44-67, 2008. Google Scholar
  28. Madhav Jha and Sofya Raskhodnikova. Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM J. Comput., 42(2):700-731, 2013. Google Scholar
  29. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric type theorems. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 52-58, 2015. Google Scholar
  30. Subhash Khot and Igor Shinkar. An Õ(n) queries adaptive tester for unateness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, pages 37:1-37:7, 2016. Google Scholar
  31. Eric Lehman and Dana Ron. On disjoint chains of subsets. J. Combin. Theory Ser. A, 94(2):399-404, 2001. Google Scholar
  32. Sofya Raskhodnikova. Testing if an array is sorted. In Encyclopedia of Algorithms, pages 2219-2222. Springer, 2016. Google Scholar
  33. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
  34. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 222-227, 1977. 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