A characterization of constant‐sample testable properties
Eric Blais, Yuichi Yoshida · Random Structures and Algorithms · 2018
Abstract We characterize the set of properties of Boolean‐valued functions on a finite domain that are testable with a constant number of samples (x,f(x)) withxdrawn uniformly at random from . Specifically, we show that a property is testable with a constant number of samples if and only if it is (essentially) ak‐part symmetric property for some constantk, where a property isk‐part symmetric if there is a partition of such that whether satisfies the property is determined solely by the densities offon . 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 , monotonicity of functions on thed‐dimensional hypergrid is testable with a constant number of samples.