Invariance in Property Testing
Madhu Sudan
Microsoft Research
The goal of Property Testing is to design highly efficient algorithms
that sample very small portions of massive data to detect if the data
satisfies some global property. 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 (or a large field) in the testing of algebraic properties.
Based on works of/with: Tali Kaufman, Shachar Lovett, Eli Ben-Sasson, Elena
Grigorescu, Ghid Maatouk and Amir Shpilka.