Property Testing

Core Idea

Property testing asks whether an input has a specific property or is "far" from having it, using a number of queries sublinear in the input size. An input is epsilon-far from a property if more than an epsilon fraction of the input must change to satisfy the property. A property tester must accept inputs with the property (with probability >= 2/3) and reject inputs that are epsilon-far (with probability >= 2/3). Blum, Luby, and Rubinfeld initiated the field with a tester for linearity of Boolean functions using O(1/epsilon) queries. Goldreich, Goldwasser, and Ron showed that many graph properties (bipartiteness, k-colorability, having a large clique) are testable in the dense graph model with query complexity depending only on epsilon, independent of graph size. The field reveals a fundamental classification of properties by their query complexity.

Explainer

Property testing sits at the intersection of sublinear algorithms and computational complexity. The question is precise: given query access to an input, can you distinguish "has property P" from "is epsilon-far from P" using few queries? The formal definition requires the tester to accept inputs with P with probability at least 2/3 and reject inputs epsilon-far from P with probability at least 2/3. Inputs that are close-but-not-satisfying may be handled either way — the definition only constrains the two extremes.

The BLR linearity test is the historical starting point. Given a function f: {0,1}^n -> {0,1}, the test picks random x, y and checks f(x) XOR f(y) = f(x XOR y). If f is linear, this always passes. If f is epsilon-far from linear, it fails with probability at least epsilon per test. The proof uses Fourier analysis: a function's distance from linearity equals the fraction of its Fourier weight outside the linear characters, and this fraction lower-bounds the test's rejection probability. Three queries per test, O(1/epsilon) tests, independent of n — this is sublinear in the most dramatic sense.

Graph property testing brings geometric and combinatorial structure into play. In the dense graph model (n² possible edges, adjacency matrix access), many properties are testable with query complexity independent of n. The regularity lemma is the key tool: it guarantees that any dense graph can be approximated by a partition of bounded size (depending only on epsilon), and properties that depend on the graph's global structure can be evaluated on this partition. In the bounded-degree (sparse) model, the picture is different: queries reveal less information per step, and many properties require sqrt(n) or more queries. Bipartiteness testing illustrates both models: O(poly(1/epsilon)) queries in the dense model, but Theta(sqrt(n)/epsilon^O(1)) in the bounded-degree model.

The classification of properties by query complexity is the central theoretical project. Which properties are testable with O(1/epsilon) queries? Which require poly(n) queries? The answers depend on the query model, the error type (one-sided vs two-sided), and the property's combinatorial structure. Recent breakthroughs have shown that in the dense graph model, the testable properties are essentially characterized by Szemerédi's regularity lemma, while in the sparse model, the picture is more complex and connects to local algorithms, distributed computing, and the theory of graph limits.