Omri Ben-Eliezer
Optimal testing of local properties via spherical queries

Abstract: A property of d-dimensional arrays is considered k-local if
the set of k * ... * k consecutive sub-arrays of a given array
completely determines whether the array satisfies the property.  We
present a simple yet canonical and powerful alphabet-independent
non-adaptive one-sided error approach to test any k-local property
over any finite (and not necessarily bounded-size) alphabet, based on
querying sphere-like structures of varying sizes. The query complexity
turns out to be optimal for a very wide range of parameters, and for
the case d=1 it even matches the two-sided adaptive query complexity
of monotonicity.