A Characterization of Constant-Sample Testable Properties

Abstract

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\}$ is testable with a constant number of samples if and only if whether $f$ satisfies $\mathcal{P}$ is (essentially) determined by the density of $f$. (iii) For every constant $d\ge 1$, monotonicity of functions $f:[n{]}^d\to \{0,1\}$ on the $d$-dimensional hypergrid is testable with a constant number of samples.