Document Open Access Logo

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces

Authors Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.38.pdf
  • Filesize: 0.66 MB
  • 21 pages

Document Identifiers

Author Details

Xi Chen
Rocco A. Servedio
Li-Yang Tan
Erik Waingarten

Cite As Get BibTex

Xi Chen, Rocco A. Servedio, Li-Yang Tan, and Erik Waingarten. Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.38

Abstract

We give a poly(log(n),1/epsilon)-query adaptive algorithm for testing whether an unknown Boolean function f:{-1, 1}^n -> {-1, 1}, which is promised to be a halfspace, is monotone versus epsilon-far from monotone. Since non-adaptive algorithms are known to require almost Omega(n^{1/2}) queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces.

Subject Classification

Keywords
  • property testing
  • linear threshold functions
  • monotonicity
  • adaptivity

Metrics

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

References

  1. N. Ailon, B. Chazelle, S. Comandur, and D. 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. 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
  3. T. Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of the 36th ACM Symposium on Theory of Computing, pages 381-390, 2004. Google Scholar
  4. A. Belovs and E. Blais. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th ACM Symposium on Theory of Computing, 2016. Google Scholar
  5. 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
  6. E. Blais, J. Brody, and K. Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. Google Scholar
  7. E. Blais, S. Raskhodnikova, and G. Yaroslavtsev. Lower bounds for testing properties of functions on hypergrid domains. Electronic Colloquium on Computational Complexity (ECCC), 20:36, 2013. Google Scholar
  8. J. Briët, S. Chakraborty, D. García-Soriano, and A. Matsliah. Monotonicity testing and shortest-path routing on the cube. Combinatorica, 32(1):35-53, 2012. Google Scholar
  9. C. Canonne, D. Ron, and R. Servedio. Testing probability distributions using conditional samples. SIAM Journal on Comput., 44(3):540-616, 2015. Google Scholar
  10. D. Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions over the hypercube. In Proceedings of the 45th ACM Symposium on Theory of Computing, pages 411-418, 2013. Google Scholar
  11. D. Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proceedings of the 45th ACM Symposium on Theory of Computing, pages 419-428, 2013. Google Scholar
  12. D. Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing, 10(17):453-464, 2014. Google Scholar
  13. X. Chen, A. De, R. A. Servedio, and L.-Y. Tan. Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries. In Proceedings of the 47th ACM Symposium on Theory of Computing, pages 519-528, 2015. Google Scholar
  14. X. Chen, R. A. Servedio, and L.-Y. Tan. New algorithms and lower bounds for monotonicity testing. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, pages 286-295, 2014. Google Scholar
  15. 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
  16. 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
  17. Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky. Improved testing algorithms for monotonocity. In Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, pages 97-108, 1999. Google Scholar
  18. D. Dzindzalieta. Tight Bernoulli tail probability bounds. Technical Report Doctoral Dissertation, Physical Sciences, Mathematics (01 P), Vilnius University, 2014. Google Scholar
  19. F. Ergün, S. Kannan, S. R. Kumar, R. Rubinfeld, and M. Vishwanthan. Spot-checkers. Journal of Computer and System Sciences, 60:717-751, 2000. Google Scholar
  20. W. Feller. An introduction to probability theory and its applications. John Wiley &Sons, 1968. Google Scholar
  21. E. Fischer. On the strength of comparisons in property testing. Information and Computation, 189(1):107-116, 2004. Google Scholar
  22. E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, pages 474-483, 2002. Google Scholar
  23. O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing monotonicity. Combinatorica, 20(3):301-337, 2000. Google Scholar
  24. S. Halevy and E. Kushilevitz. Testing monotonicity over graph products. Random Structures and Algorithms, 33(1):44-67, 2008. Google Scholar
  25. S. Khot, D. Minzer, and M. Safra. On monotonicity testing and boolean isoperimetric type theorems. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science, pages 52-58, 2015. Google Scholar
  26. K. Matulef, R. O'Donnell, R. Rubinfeld, and R. Servedio. Testing halfspaces. SIAM Journal on Comput., 39(5):2004-2047, 2010. Google Scholar
  27. D. Ron, R. Rubinfeld, M. Safra, A. Samorodnitsky, and O. Weinstein. Approximating the influence of monotone Boolean functions in O(√n) query complexity. ACM Transactions on Computation Theory, 4(4):1-12, 2012. Google Scholar
  28. D. Ron and R. A. Servedio. Exponentially improved algorithms and lower bounds for testing signed majorities. Algorithmica, 72(2):400-429, 2015. Google Scholar
  29. R. Rubinfeld and R. A. Servedio. Testing monotone high-dimensional distributions. Random Structures and Algorithms, 34(1):24-44, 2009. URL: http://dx.doi.org/10.1002/rsa.20247.
  30. R. A. Servedio, L.-Y. Tan, and J. Wright. Adaptivity helps for testing juntas. In Proceedings of the 30th IEEE Conference on Computational Complexity, pages 264-279, 2015. 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