2026-07-23T05:17:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10104 2024-03-06T10:45:23Z ddc:004 open_access

Testing Local Properties of Arrays Ben-Eliezer, Omri Property Testing Local Properties Monotonicity Testing Hypergrid Pattern Matching 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Omri Ben-Eliezer 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.11 urn:nbn:de:0030-drops-101041 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.11 eng https://creativecommons.org/licenses/by/3.0/legalcode