Invariance in Property Testing

Madhu Sudan (MSR New England)

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 the first part of the talk we survey some of the work done in testing linear properties over domains that are vector spaces over some field, and the property is invariant under the group of invertible affine transformations. In particular we show how this abstracts the most common algebraic error-correcting codes and how the most basic testing result applies to the abstract class. We also give some new properties that fall in this general class that outperform the classically studied codes in terms of locality.

In the second part of the talk, we revisit the most central affine-invariant property, namely: Given a function f:F_q^n to F_q, where F_q denotes the finite field on q elements, test if f is a polynomial of degree at most d. Different solutions to this basic question, for different ranges of parameters n,q,d, have had immense applications in complexity theory. In this talk we focus on the case where q is a constant and d is slowly growing. We consider tha natural ``affine-invariance'' based test: Verify that f restrict to t-dimensional subspaces is a polynomial of degree at most d (where t is some small integer depending only on d and q).  We show essentially optimal analysis of this test; and mention some recently discovered applications.

First part is based on works of/with: Tali Kaufman, Shachar Lovett, Eli Ben-Sasson, Elena Grigorescu, Alan Guo, Swastik Kopparty, Ghid Maatouk, and Amir Shpilka.

Second part based on works with: Arnab Bhattacharyya, Elad Haramaty, Swastik Kopparty, Noga Ron-Zewi, Grant Schoenebeck, Amir Shpilka, and David Zuckerman