We characterize the set of properties of Boolean-valued functions on a finite domain that are testable with a constant number of samples. Specifically, we show that a property 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 k -part symmetric if there is a partition S 1 S k of such that whether f : 0 1 satisfies the property is determined solely by the densities of f on S 1 S k .

We use this characterization to obtain a number of corollaries, namely: (i) A graph property is testable with a constant number of samples if and only if whether a graph G satisfies is (essentially) determined by the edge density of G . (ii) An affine-invariant property of functions f : F n p 0 1 is testable with a constant number of samples if and only if whether f satisfies 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.