A characterization of constant‐sample testable properties

We characterize the set of properties of Boolean‐valued functions f : X → { 0 , 1 } on a finite domain X that are testable with a constant number of samples ( x,f ( x )) with x drawn uniformly at random from X . 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 k ‐part symmetric if there is a partitionX 1 , … , X kof X such that whether f : X → { 0 , 1 } satisfies the property is determined solely by the densities of f onX 1 , … , X k . We use this characterization to show that symmetric properties are essentially the only graph properties and affine‐invariant properties that are testable with a constant number of samples and that for every constant d ≥ 1 , monotonicity of functions on the d ‐dimensional hypergrid is testable with a constant number of samples.