One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem seems very difficult in general. In this paper, we identify a wide class of properties of ordered structures - the earthmover resilient (ER) properties - and show that the "good behavior" of such properties allows us to obtain general testability results that are similar to (and more general than) those of unordered graphs. A property P is ER if, roughly speaking, slight changes in the order of the elements in an object satisfying P cannot make this object far from P. The class of ER properties includes, e.g., all unordered graph properties, many natural visual properties of images, such as convexity, and all hereditary properties of ordered graphs and images. A special case of our results implies, building on a recent result of Alon and the authors, that the distance of a given image or ordered graph from any hereditary property can be estimated (with good probability) up to a constant additive error, using a constant number of queries.
The notion of a sample-based test, already defined in the seminal work of Goldreich, Goldwasser and Ron @cite_8 , refers to tests that cannot choose which queries to make. A @math -query test for @math is if it receives pairs of the form @math where @math is the unknown input function and @math are picked uniformly at random from the domain of @math (compare this to the definition of canonical tests from Subsection ). A recent work of Blais and Yoshida @cite_13 characterizes the properties @math that have a constant query test.
@cite_13 @cite_8
2950427777 1970630090
We characterize the set of properties of Boolean-valued functions on a finite domain @math that are testable with a constant number of samples. Specifically, we show that a property @math is testable with a constant number of samples if and only if it is (essentially) a @math -part symmetric property for some constant @math , where a property is @math -part symmetric if there is a partition @math of @math such that whether @math satisfies the property is determined solely by the densities of @math on @math . We use this characterization to obtain a number of corollaries, namely: (i) A graph property @math is testable with a constant number of samples if and only if whether a graph @math satisfies @math is (essentially) determined by the edge density of @math . (ii) An affine-invariant property @math of functions @math is testable with a constant number of samples if and only if whether @math satisfies @math is (essentially) determined by the density of @math . (iii) For every constant @math , monotonicity of functions @math on the @math -dimensional hypergrid is testable with a constant number of samples. In this paper, we consider the question of determining whether a function f has property P or is e-far from any function with property P. A property testing algorithm is given a sample of the value of f on instances drawn according to some distribution. In some cases, it is also allowed to query f on instances of its choice. We study this question for different properties and establish some connections to problems in learning theory and approximation. In particular, we focus our attention on testing graph properties. Given access to a graph G in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has properties such as being bipartite, k -Colorable, or having a p -Clique (clique of density p with respect to the vertex set). Our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is independent of the size of the graph. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.