Invariance in Property Testing
Madhu Sudan
Microsoft Research
The goal of Property Testing is to design highly efficient algorithms samples very small portions of massive data to detect if the data satisfies some global properties. As ambitious as this goal may sound, research in the past two decades has shown that a wide variety of properties, looking for statistical, combinatorial, graph-theoretic, or algebraic structure in data, can be tested surprisingly efficiently. In this talk we will explain how the ``invariance'' of the property has played a role, mostly implicitly and recently explicitly, in the success of property testing.
A property is said to be invariant under a permutation pi if permuting the data points by this permutation leaves the property unchanged. The set of permutations that keep a property invariant forms a group under composition, and many of the above different themes in property testing can be classified based on the invariant group of the property. In this talk we stress in particular the role of the affine group on vector spaces in the testing of algebraic properties.