Property Testing and Affine-Invariance
Madhu Sudan (Harvard)
Property testing considers the task of testing if a given function satisfies some nice property, *without* querying the function everywhere. Testing of algebraic properties in particular leads to extremely interesting mathematical questions, and the answers have had major consequences to theoretical computer science in the past two decades. The prototypical question here considers the task of testing if an m-variate function over a finite field is a polynomial of degree d. Whereas the number of coefficients specifying such a function could be exponentially large in minimum(m,d), one of the major results in the field shows that the number of queries needed to test this property is only linear in d (for sufficiently large fields).
In these two lectures I will introduce an abstraction of the property of being a low-degree polynomial, namely "affine-invariance" - wherein the property being tested in closed under affine transformations of the domain. This abstraction presents a clean way to unify many results in the literature and strengthen and extend them. In the talks I will formally introduce affine-invariant properties, describe some structural results about affine-invariance and show some new affine-invariant properties that are denser than the class of low-degree polynomials. I will describe how the analysis of property tests is carried out in this abstract setting - strikingly the generality of the abstract setting forces the proofs to be simpler! I will conclude with a conjecture on the testability of affine-invariant properties.
Based on joint works with many collaborators including Tali Kaufman, Elena Grigorescu, Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Noga Ron-Zewi, Alan Guo, Swastik Kopparty, and Elad Haramaty.