We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of d -dimensional arrays f : [ n ] d is k -local if it can be defined by a family of k 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 -test, whose query complexity is O ( − 1 k log k n ) for d = 1 and O ( c d − 1 d k n d − 1 ) for 1"> 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 . 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 1"> 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.