A characterization of constant‐sample testable properties. Issue 1 (19th September 2018)

• Record Type: Journal Article
• Authors: Blais, Eric; Yoshida, Yuichi
• Is Part Of: Random structures & algorithms. Volume 55:Issue 1(2019)
• Page Start: 73
• Page End: 88
• Publication Date: 2018-09-19
• Subjects: Property testing -- sample complexity -- partial symmetry; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20807
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 partition X 1, …, X k of X such that whether f : X → { 0, 1 } satisfies the property is determined solely by the densities of f on X 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.