Testing Local Properties of Arrays

Author Omri Ben-Eliezer



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.11.pdf
  • Filesize: 463 kB
  • 20 pages

Document Identifiers

Author Details

Omri Ben-Eliezer
  • Tel Aviv University, Tel Aviv 69978, Israel

Cite AsGet BibTex

Omri Ben-Eliezer. Testing Local Properties of Arrays. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.11

Abstract

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of d-dimensional arrays f:[n]^d -> Sigma is k-local if it can be defined by a family of k x ... x k forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and submodularity are 2-local; convexity is (usually) 3-local; and many typical problems in computational biology and computer vision involve o(n)-local properties. In this work, we present a generic approach to test all local properties of arrays over any finite (and not necessarily bounded size) alphabet. We show that any k-local property of d-dimensional arrays is testable by a simple canonical one-sided error non-adaptive epsilon-test, whose query complexity is O(epsilon^{-1}k log{(epsilon n)/k}) for d = 1 and O(c_d epsilon^{-1/d} k * n^{d-1}) for d > 1. The queries made by the canonical test constitute sphere-like structures of varying sizes, and are completely independent of the property and the alphabet Sigma. The query complexity is optimal for a wide range of parameters: For d=1, this matches the query complexity of many previously investigated local properties, while for d > 1 we design and analyze new constructions of k-local properties whose one-sided non-adaptive query complexity matches our upper bounds. For some previously studied properties, our method provides the first known sublinear upper bound on the query complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
Keywords
  • Property Testing
  • Local Properties
  • Monotonicity Testing
  • Hypergrid
  • Pattern Matching

Metrics

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

References

  1. N. Alon, O. Ben-Eliezer, and E. Fischer. Testing Hereditary Properties of Ordered Graphs and Matrices. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 848-858, 2017. Google Scholar
  2. N. Alon, M. Krivelevich, I. Newman, and M. Szegedy. Regular languages are testable with a constant number of queries. SIAM Journal on Computing, 30:1842-1862, 2001. Google Scholar
  3. P. Awasthi, M. Jha, M. Molinaro, and S. Raskhodnikova. Testing Lipschitz functions on hypergrid domains. Algorithmica, 74:1055-1081, 2016. Google Scholar
  4. A. Belovs. Adaptive Lower Bound for Testing Monotonicity on the Line. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 31:1-31:10, 2018. Google Scholar
  5. O. Ben-Eliezer. Testing local properties of arrays. Electronic Colloquium on Computational Complexity (ECCC), 2018. full version. URL: https://eccc.weizmann.ac.il/report/2018/196/.
  6. O. Ben-Eliezer and E. Fischer. Earthmover Resilience and Testing in Ordered Structures. In Proceedings of the 33rd Conference on Computational Complexity (CCC), pages 18:1-18:35, 2018. Google Scholar
  7. O. Ben-Eliezer, S. Korman, and D. Reichman. Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP), pages 9:1-9:14, 2017. Google Scholar
  8. P. Berman, M. Murzabulatov, and S. Raskhodnikova. Testing convexity of figures under the uniform distribution. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG), pages 17:1-17:15, 2016. Google Scholar
  9. P. Berman, M. Murzabulatov, and S. Raskhodnikova. Tolerant testers of image properties. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 90:1-90:14, 2016. Google Scholar
  10. P. Berman, S. Raskhodnikova, and G. Yaroslavtsev. L_p-testing. In Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC), pages 164-173, 2014. Google Scholar
  11. E. Blais and A. Bommireddi. Testing submodularity and other properties of valuation functions. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), pages 33:1-33:17, 2017. Google Scholar
  12. E. Blais, J. Brody, and K. Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21:311-358, 2012. Google Scholar
  13. E. Blais, S. Raskhodnikova, and G. Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In Proceedings of the 29th Conference on Computational Complexity (CCC), pages 309-320, 2014. Google Scholar
  14. D. Chakrabarty. Monotonicity testing. Encyclopedia of Algorithms, pages 1352-1356, 2016. Google Scholar
  15. D. Chakrabarty, K. Dixit, M. Jha, and C. Seshadhri. Property testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. ACM Transactions on Algorithms, 13:20:1-20:30, 2017. Google Scholar
  16. D. Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC), pages 419-428, 2013. Google Scholar
  17. D. Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. Theory of Computing, 10:453-464, 2014. Google Scholar
  18. X. Chen, A. Freilich, R. Servedio, and T. Sun. Sample-based high-dimensional convexity testing. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 37:1-37:20, 2017. Google Scholar
  19. F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan. Spot-checkers. Journal of Computer and System Sciences, 60:717-751, 2000. Google Scholar
  20. E. Fischer. On the strength of comparisons in property testing. Information and Computation, 25:107-116, 2004. Google Scholar
  21. O. Goldreich. Introduction to property testing. Cambridge University Press, 2017. Google Scholar
  22. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45:653-750, 1998. Google Scholar
  23. O. Goldreich and D. Ron. On proximity-oblivious testing. SIAM Journal on Computing, 40:534-566, 2011. Google Scholar
  24. M. Jha and S. Raskhodnikova. Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM Journal on Computing, 42:700-731, 2013. Google Scholar
  25. S. Korman, D. Reichman, G. Tsur, and S. Avidan. Fast-Match: Fast Affine Template Matching. International Journal of Computer Vision, 121:111-125, 2017. Google Scholar
  26. S. Moriguchi and K. Murota. On discrete Hessian matrix and convex extendability. Journal of the Operations Research Society of Japan, 55:48-62, 2012. Google Scholar
  27. K. Murota. Discrete Convex Analysis. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  28. I. Newman and C. Sohler. Every property of hyperfinite graphs is testable. SIAM Journal on Computing, 42:1095-1112, 2013. Google Scholar
  29. R. Pallavoor, S. Raskhodnikova, and N. Varma. Parameterized property testing of functions. ACM Transactions on Computation Theory, 9:17:1-17:19, 2018. Google Scholar
  30. M. Parnas, D. Ron, and R. Rubinfeld. On testing convexity and submodularity. SIAM Journal on Computing, 32:1158-184, 2003. Google Scholar
  31. L. Rademacher and S. Vempala. Testing geometric convexity. In Foundations of Software Technology and Theoretical Computer Science Conference (FSTTCS), pages 469-480, 2004. Google Scholar
  32. S. Raskhodnikova. Testing if an array is sorted. Encyclopedia of Algorithms, pages 2219-2222, 2016. Google Scholar
  33. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25:252-271, 1996. Google Scholar
  34. C. Seshadhri and Jan Vondrák. Is Submodularity Testable? Algorithmica, 69:1-25, 2014. Google Scholar
  35. A. C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual 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