Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-196 | 19th November 2018 03:10

Testing local properties of arrays

RSS-Feed




TR18-196
Authors: Omri Ben-Eliezer
Publication: 19th November 2018 21:11
Downloads: 820
Keywords: 


Abstract:

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of d-dimensional arrays f:[n]^d \to \Sigma is k-local if it can be defined by a family of k \times \ldots \times 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 \varepsilon-test, whose query complexity is O(\epsilon^{-1}k \log{\frac{\epsilon n}{k}}) for d = 1 and O(c_d \epsilon^{-1/d} k \cdot 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.



ISSN 1433-8092 | Imprint