A characterization of constant‐sample testable properties. Issue 1 (19th September 2018) - Blais, Eric; Yoshida, Yuichi
Abstract: 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 partition X 1, …, X k of X such that whether f : X → 0, 1 satisfies the property is determined solely by the densities of f on X 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.