2016/12/19 by Eric Blais, Yuichi Yoshida, Blais, Eric +1 · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1612.06016
openalex publication_date 2016/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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,…,Sk of X such that whether f:X → \0,1\ satisfies the property is determined solely by the densities of f on S1,…,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.