Seminar: October 18

Madhu Sudan, Microsoft Research, Boston

Invariance in Property Testing

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.