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 k-part symmetric if there is a partition S 1 , . . . , S k of X such that whether f : X → {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: • 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.
A recent work of Blais and Yoshida REF characterizes the properties P that have a constant query sample-based test.
A Characterization of Constant-Sample Testable Properties
ArXiv
ArXiv
Computer Science Mathematics