Document Open Access Logo

Adaptive Lower Bound for Testing Monotonicity on the Line

Author Aleksandrs Belovs

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.31.pdf
  • Filesize: 386 kB
  • 10 pages

Document Identifiers

Author Details

Aleksandrs Belovs
  • Faculty of Computing, University of Latvia, Raina bulvaris 19, Riga, Latvia.

Funding

This research is supported by the ERDF project number 1.1.1.2/I/16/113.
  • Belovs, Aleksandrs: supported by the ERDF project number 1.1.1.2/I/16/113

Cite As Get BibTex

Aleksandrs Belovs. Adaptive Lower Bound for Testing Monotonicity on the Line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 31:1-31:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.31

Abstract

In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this paper we study query complexity of epsilon-testing monotonicity of a function f : [n]->[r]. All our lower bounds are for adaptive two-sided testers. 
- We prove a nearly tight lower bound for this problem in terms of r. The bound is Omega((log r)/(log log r)) when epsilon = 1/2. No previous satisfactory lower bound in terms of r was known.
- We completely characterise query complexity of this problem in terms of n for smaller values of epsilon. The complexity is Theta(epsilon^{-1} log (epsilon n)). Apart from giving the lower bound, this improves on the best known upper bound.
Finally, we give an alternative proof of the Omega(epsilon^{-1}d log n - epsilon^{-1}log epsilon^{-1}) lower bound for testing monotonicity on the hypergrid [n]^d due to Chakrabarty and Seshadhri (RANDOM'13).

Subject Classification

ACM Subject Classification
  • Theory of computation → Lower bounds and information complexity
Keywords
  • property testing
  • monotonicity on the line
  • monotonicity on the hypergrid

Metrics

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

References

  1. Aleksandrs Belovs and Eric Blais. Quantum algorithm for monotonicity testing on the hypercube. Theory of Computing, 11(16):403-412, 2015. Google Scholar
  2. Aleksandrs Belovs and Eric Blais. A polynomial lower bound for testing monotonicity. In Proc. of 48th ACM STOC, pages 1021-1032, 2016. Google Scholar
  3. Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. Google Scholar
  4. Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In Proc. of 29th IEEE CCC, pages 309-320, 2014. Google Scholar
  5. Deeparnab Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing, 10:453-464, 2014. Google Scholar
  6. Deeparnab Chakrabarty and Comandur Seshadhri. A o(n) monotonicity tester for Boolean functions over the hypercube. In Proc. of 45th ACM STOC, pages 411-418, 2013. Google Scholar
  7. Deeparnab Chakrabarty and Comandur Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proc. of 45th ACM STOC, pages 419-428, 2013. Google Scholar
  8. Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries. In Proc. of 47th ACM STOC, pages 519-528, 2015. Google Scholar
  9. Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In Proc. of 55th IEEE FOCS, pages 286-295, 2014. Google Scholar
  10. Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. In Proc. of 49th ACM STOC, pages 523-536, 2017. Google Scholar
  11. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In Proc. of 3rd, pages 97-108. Springer, 1999. Google Scholar
  12. Funda" Ergün, Sampath" "Kannan, S Ravi" "Kumar, Ronitt" "Rubinfeld, and Mahesh "Viswanathan. Spot-checkers. Journal of Computer and System Sciences, 60(3):717-751, 2000. Google Scholar
  13. Eldar Fischer. On the strength of comparisons in property testing. Information and Computation, 189(1):107-116, 2004. Google Scholar
  14. Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset domains. In Proc. of 34th ACM STOC, pages 474-483, 2002. Google Scholar
  15. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301-337, 2000. Google Scholar
  16. Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, 1998. Google Scholar
  17. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and Boolean isoperimetric type theorems. In Proc. of 56th IEEE FOCS, pages 52-58, 2015. Google Scholar
  18. Ramesh Krishnan S Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized property testing of functions. In Proc. of 8th ACM ITCS, volume 67 of LIPIcs, page 12. Dagstuhl, 2017. Google Scholar
  19. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. 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