Premium
A characterization of constant‐sample testable properties
Author(s) -
Blais Eric,
Yoshida Yuichi
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20807
Subject(s) - constant (computer programming) , mathematics , characterization (materials science) , monotonic function , affine transformation , property testing , property (philosophy) , constant function , partition (number theory) , combinatorics , invariant (physics) , discrete mathematics , pure mathematics , mathematical analysis , physics , piecewise , computer science , philosophy , epistemology , optics , mathematical physics , programming language
We characterize the set of properties of Boolean‐valued functions f : X → { 0 , 1 } on a finite domain X that are testable with a constant number of samples ( x,f ( x )) with x drawn uniformly at random from X . 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 k ‐part symmetric if there is a partitionX 1 , … , X kof X such that whether f : X → { 0 , 1 } satisfies the property is determined solely by the densities of f onX 1 , … , X k . We use this characterization to show that symmetric properties are essentially the only graph properties and affine‐invariant properties that are testable with a constant number of samples and that for every constant d ≥ 1 , monotonicity of functions on the d ‐dimensional hypergrid is testable with a constant number of samples.