A characterization of constant-sample testable properties

DOI10.1002/RSA.20807MaRDI QIDQ5236924zbMATH OpenOpenAlexWikidataFDO

Authors Eric Blais, Yuichi Yoshida

Publication date 16 October 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06016

zbMATH Keywords

property testingsample complexitypartial symmetry

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Abstract: We characterize the set of properties of Boolean-valued functions on a finite domain $mathcalX$ that are testable with a constant number of samples. Specifically, we show that a property $mathcalP$ 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 $S_1,ldots,S_k$ of $mathcalX$ such that whether $f:mathcalXo0,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 $mathcalP$ is testable with a constant number of samples if and only if whether a graph $G$ satisfies $mathcalP$ is (essentially) determined by the edge density of $G$. (ii) An affine-invariant property $mathcalP$ of functions $f:mathbb{F}_p^{n}o0,1$ is testable with a constant number of samples if and only if whether $f$ satisfies $mathcalP$ is (essentially) determined by the density of $f$. (iii) For every constant $dgeq1$, monotonicity of functions $f:[n{]}^{d}o0,1$ on the $d$-dimensional hypergrid is testable with a constant number of samples.

Recommendations

• Testing properties of graphs and functions
• Algebraic property testing: the role of invariance
• Property testing. Problems and techniques
• A canonical form for testing Boolean function properties
• A characterization of locally testable affine-invariant properties via decomposition theorems

Cites work

• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A characterization of locally testable affine-invariant properties via decomposition theorems
• A unified framework for testing linear-invariant properties
• Algebraic property testing: the role of invariance
• An algebraic characterization of testable Boolean CSPs
• Invariance in property testing
• Monotonicity testing over general poset domains
• On Sample-Based Testers
• On active and passive testing
• Partial tests, universal tests and decomposability
• Partially symmetric functions are efficiently isomorphism testable
• Property testing and its connection to learning and approximation
• Property testing. Current research and surveys
• Robust Characterizations of Polynomials with Applications to Program Testing
• Szemerédi's regularity lemma revisited
• Testing monotonicity
• Testing problems with sublearning sample complexity
• The final form of Tao's inequality relating conditional expectation and conditional mutual information
• Three theorems regarding testing graph properties

Cited in

(7)

• Attribute estimation and testing quasi-symmetry
• Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
• A canonical form for testing Boolean function properties
• Testing properties of graphs and functions
• Property Testing on Product Distributions
• Sample-based high-dimensional convexity testing
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions

This page was built for publication: A characterization of constant-sample testable properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236924)