Movatterモバイル変換

[0]ホーム
URL:

DocumentOpen Access Logo
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.38

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces

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

PDF

File

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

Document Identifiers

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

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.

Cite AsGet 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

Author Details

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

          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 anE-mail
          © 2023-2025Schloss Dagstuhl – LZI GmbHAbout DROPSImprintPrivacyContact
          [8]ページ先頭
          ©2009-2025 Movatter.jp