The Role of Invariance in Property Testing

Madhu Sudan
Microsoft Research New England

Property testing considers the task of testing if some given data satisfies a desired property by sampling the data probabilistically in very few places. The ``oldest'' property test might be the use of polling to predict the outcome of an upcoming election. Modern research has extended the scope of property tests to a much richer class of properties including tests of linearity ("is the data essentially linear with respect to some parameters"), multilinearity, low-degreeness, colorability ("is the data describing a graph with small chromatic number") etc.

What makes some properties testable so efficiently, that we do not have to look at the entire data in order to test for it? We suggest that for interesting properties, testability ought to be related to the "invariances" shown by the property: i.e., if the data is viewed as a function from some input to some output, then the "invariances" are given by a set (a group) of permutations of the input space under which the property is invariant. We then investigate this hypothesis in the context of "algebraic properties". This leads to a rich unification of previous known works, as also some new properties and counterexamples to more optimistic conjectures.

Based on joint works with Elena Grigorescu and Tali Kaufman (MIT).

Back to Workshop IV: Analytical Methods in Combinatorics, Additive Number Theory and Computer Science