ECCC-Report TR16-201https://eccc.weizmann.ac.il/report/2016/201Comments and Revisions published for TR16-201en-usMon, 19 Dec 2016 05:25:18 +0200
Paper TR16-201
| A Characterization of Constant-Sample Testable Properties |
Eric Blais,
Yuichi Yoshida
https://eccc.weizmann.ac.il/report/2016/201We 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 $k$-part symmetric if there is a partition $S_1,\ldots,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,\ldots,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 \geq 1$, monotonicity of functions $f : [n]^d \to \{0, 1\}$ on the $d$-dimensional hypergrid is testable with a constant number of samples.
Mon, 19 Dec 2016 05:25:18 +0200https://eccc.weizmann.ac.il/report/2016/201