# A Characterization of Constant-Sample Testable Properties

arXiv: https://arxiv.org/abs/1612.06016 · HTML: https://mlsanity.com/paper/1612.06016/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2016.

## Built on by (most cited first, 1 of 1)

- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)

## Abstract (arXiv)

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 em k-part symmetric if there is a partition S1,ldots,Sk of X such that whether f:X → 0,1 satisfies the property is determined solely by the densities of f on S1,ldots,Sk. We use this characterization to obtain a number of corollaries, namely: (i) 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. (ii) An affine-invariant property P of functions f:mathbbFpn → 0,1 is testable with a constant number of samples if and only if whether f satisfies P is (essentially) determined by the density of f. (iii) For every constant d ≥ 1, monotonicity of functions f : [n]d → 0, 1 on the d-dimensional hypergrid is testable with a constant number of samples.