A Characterization of Constant-Sample Testable Properties

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples. Specifically, we show that a property $\mathcal{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 {\em $k$-part symmetric} if there is a partition $S_1,\dots ,S_k$ of $\mathcal{X}$ such that whether $f:\mathcal{X}\to \{0,1\}$ satisfies the property is determined solely by the densities of $f$ on $S_1,\dots ,S_k$. We use this characterization to obtain a number of corollaries, namely: (i) A graph property $\mathcal{P}$ is testable with a constant number of samples if and only if whether a graph $G$ satisfies $\mathcal{P}$ is (essentially) determined by the edge density of $G$. (ii) An affine-invariant property $\mathcal{P}$ of functions $f:$\mathbb{F}$_p^n \to {0,1}$istestablewithaconstantnumberofsamplesifandonlyifwhether$f$satisfies$$\mathcal{P}$$is(essentially)determinedbythedensityof$f$. (iii) For every constant $d\ge 1$, monotonicity of functions $f : [n]^d \to {0, 1}$onthe$d$-dimensional hypergrid is testable with a constant number of samples.