Abstract

Property testing is concerned with determining whether an unknown function has a given property. The decision problem in this context is relaxed in the following two senses: first, we are given the promise that either the property is satisfied or the function is “far” from satisfying the property, and second, we are allowed to fail with some small error probability. The slackness introduced allows us to build extremely fast testers, even ones that run in time sublinear in the size of the input. This necessarily requires the algorithm to have sublinear query complexity, namely that it only reads in/queries a fraction of the input. We explore the area of property testers with two illustrative example problems: testing whether a given graph is bipartite and whether a binary input sequence does not contain a fixed string as a subsequence. We conclude with a brief survey on related areas and their connections to property testing.