Combinatorial property testing, initiated by Rubinfeld and Sudan 96, and formally defined by Goldreich, Goldwasser and Ron 96, deals with the following relaxation of decision problems: Given a fixed property and an input f, one wants to decide whether f has the property or is `far' from having the property.

Here we concentrate on 0/1 labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e as a product order of the total order). The main result is that every property of 0/1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets is efficiently testable, namely: There is a randomized algorithm that for such a property on d-dimensional grids with side length n, with error probability 1/3, accepts every 0/1 labeled grid that has the property while it reject labeled grids for which it is required to change at least \epsilon n^d of the entries in order for them to have the property. The query complexity is poly(1/\epsilon) and independent of n (for fixed d). Such properties include the well studied `monotonicity' property, other, more complicated forbidden chain patterns, and general forbidden poset patterns. Another result is an efficient test for a collection of bipartite graph properties.

Both collections above are variants of properties that are defined by certain first order formulae with no quantifier alteration over the syntax containing the grid order relations (and some additional relations for the bipartite graph properties). We show also that with one quantifier alteration, a certain property can be defined, for which no test with query complexity of O(n^.1) (for a small enough fixed \epsilon) exists. These results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. It also lays out a platform that bridges some previously unrelated results.

This is a joint work with Eldar Fischer.