## A Characterization of Constant-Sample Testable Properties

by Eric Blais and Yuichi Yoshida

#### Oded's comments

Characterizations of problems according to their complexity
are a cherished goal of TOC, even when one considers very
lowe levels of complexity as is the case with sample-based testability
with a constant number of samples. This work articulates the intuition
that this complexity class is indeed very restricted, and indicates
exacly what it can do.

#### The original 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 $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.

See ECCC TR16-201.

Back to
list of Oded's choices.