The Role of Invariance in Property Testing
Madhu Sudan (Microsoft Research)
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).