A Characterization of Constant-Sample Testable Properties

We characterize the set of properties of Boolean-valued functions on a finite domain X that are testable with a constant number of samples. Specifically, we show that a property P is testable with a constant number of samples if and only if it is (essentially) a k-part symmetric property for some constant k, where a property is em k-part symmetric if there is a partition S1,ldots,Sk of X such that whether f:X → 0,1 satisfies the property is determined solely by the densities of f on S1,ldots,Sk. We use this characterization to obtain a number of corollaries, namely: (i) A graph property P is testable with a constant number of samples if and only if whether a graph G satisfies P is (essentially) determined by the edge density of G. (ii) An affine-invariant property P of functions f:mathbbFpn → 0,1 is testable with a constant number of samples if and only if whether f satisfies P is (essentially) determined by the density of f. (iii) For every constant d ≥ 1, monotonicity of functions f : [n]d → 0, 1 on the d-dimensional hypergrid is testable with a constant number of samples.