Document Open Access Logo

Parameterized Property Testing of Functions

Authors Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.12.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Ramesh Krishnan S. Pallavoor
Sofya Raskhodnikova
Nithin Varma

Cite As Get BibTex

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized Property Testing of Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.12

Abstract

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us to surpass the (worst-case) lower bounds, expressed in terms of the input size, for several problems. Our aim is to develop a similar level of understanding of the complexity of sublinear-time algorithms to the one that was enabled by research in parameterized complexity for classical algorithms.

Specifically, we focus on testing properties of functions. By parameterizing the query complexity in terms of the size r of the image of the input function, we obtain testers for monotonicity and convexity of functions of the form f:[n]\to \mathbb{R} with query complexity O(\log r), with no dependence on n. The result for monotonicity circumvents the \Omega(\log n) lower bound by Fischer (Inf. Comput., 2004) for this problem. We present several other parameterized testers, providing compelling evidence that expressing the query complexity of property testers in terms of the input size is not always the best choice.

Subject Classification

Keywords
  • Sublinear algorithms
  • property testing
  • parameterization
  • monotonicity
  • convexity

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. Tugkan Batu, Ronitt Rubinfeld, and Patrick White. Fast approximate PCPs for multidimensional bin-packing problems. Inf. Comput., 196(1):42-56, 2005. Google Scholar
  3. Mihir Bellare and Phillip Rogaway. Lecture notes on modern cryptography, 2005. URL: https://cseweb.ucsd.edu/~mihir/cse207/w-birthday.pdf.
  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 of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 1021-1032, 2016. Google Scholar
  6. Sagi Ben-Moshe, Yaron Kanza, Eldar Fischer, Arie Matsliah, Mani Fischer, and Carl Staelin. Detecting and exploiting near-sortedness for efficient relational query evaluation. In Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings, pages 256-267, 2011. Google Scholar
  7. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. The power and limitations of uniform samples in testing properties of figures. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, Chennai, India, pages 45:1-45:14, 2016. Google Scholar
  8. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing convexity of figures under the uniform distribution. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, pages 17:1-17:15, 2016. Google Scholar
  9. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 164-173, 2014. Google Scholar
  10. 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
  11. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. Google Scholar
  12. Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 309-320, 2014. Google Scholar
  13. 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
  14. Deeparnab Chakrabarty. Monotonicity testing. In Encyclopedia of Algorithms, pages 1352-1356. Springer, 2016. Google Scholar
  15. Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri. Property testing on product distributions: Optimal testers for bounded derivative properties. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1809-1828, 2015. Google Scholar
  16. Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 419-428, 2013. Google Scholar
  17. Deeparnab Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing, 10:453-464, 2014. Google Scholar
  18. 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
  19. Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC'15, pages 519-528, New York, NY, USA, 2015. Google Scholar
  20. Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 286-295, 2014. Google Scholar
  21. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin M. Varma. Erasure-resilient property testing. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 91:1-91:15, 2016. Google Scholar
  22. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In RANDOM-APPROX'99, Berkeley, CA, USA, August 8-11, 1999, Proceedings, pages 97-108, 1999. Google Scholar
  23. Funda Ergün, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan. Spot-checkers. J. Comput. Syst. Sci., 60(3):717-751, 2000. Google Scholar
  24. Eldar Fischer. On the strength of comparisons in property testing. Inf. Comput., 189(1):107-116, 2004. Google Scholar
  25. Eldar Fischer, Oded Lachish, and Yadu Vasudev. Trading query complexity for sample-based testing and multi-testing scalability. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1163-1182, 2015. Google Scholar
  26. Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 474-483, 2002. Google Scholar
  27. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. 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. J. ACM, 45(4):653-750, 1998. Google Scholar
  29. Oded Goldreich and Dana Ron. On proximity-oblivious testing. SIAM J. Comput., 40(2):534-566, 2011. Google Scholar
  30. Oded Goldreich and Dana Ron. On sample-based testers. TOCT, 8(2):7, 2016. Google Scholar
  31. Shirley Halevy and Eyal Kushilevitz. A lower bound for distribution-free monotonicity testing. In APPROX-RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, pages 330-341, 2005. Google Scholar
  32. Shirley Halevy and Eyal Kushilevitz. Testing monotonicity over graph products. Random Struct. Algorithms, 33(1):44-67, 2008. Google Scholar
  33. Kazuo Iwama and Yuichi Yoshida. Parameterized testability. In Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 507-516, 2014. Google Scholar
  34. 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
  35. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and Boolean isoperimetric type theorems. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 52-58, 2015. Google Scholar
  36. Eric Lehman and Dana Ron. On disjoint chains of subsets. J. Comb. Theory, Ser. A, 94(2):399-404, 2001. Google Scholar
  37. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM J. Comput., 32(5):1158-1184, 2003. Google Scholar
  38. Sofya Raskhodnikova. Testing if an array is sorted. In Encyclopedia of Algorithms, pages 2219-2222. Springer, 2016. Google Scholar
  39. Sofya Raskhodnikova and Adam D. Smith. A note on adaptivity in testing properties of bounded degree graphs. Electronic Colloquium on Computational Complexity (ECCC), 13(089), 2006. Google Scholar
  40. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
  41. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, 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