Property testing

Property testing is a field of theoretical computer science concerned with designing very fast algorithms for approximate decision making, where the decision concerns properties or parameters of huge objects. A property testing algorithm for a decision problem has a query complexity, the number of queries made to its input, that is much smaller than the size of the problem instance. Typically it decides whether a combinatorial structure such as a graph or a boolean function satisfies some property, or is far from satisfying it, meaning that an epsilon fraction of its representation would have to change, using only a small number of local queries. For example, whether a graph on n vertices is bipartite, or cannot be made bipartite even after removing a small fraction of its edges, can be decided with a query complexity independent of n. Such algorithms are randomized, and their running time is often sublinear in the instance length. Property testing algorithms are central to the definition of probabilistically checkable proofs. The field of graph property testing was introduced by Goldreich, Goldwasser and Ron in a paper published in 1998.