Testing Affine-Invariant Properties
Madhu Sudan
Property testing studies the complexity of testing global properties of massive data by local sampling. Viewing the data as a function, a property is simply a subset of all functions. A particularly successful, and extremely useful, line of work attempts to understand the local testability of algebraic codes --- here the properties are functions that come from some nice algebraic collection (such as low-degree polynomials, or traces of low-degree polynomials), and the goal is to test if a function is close to a member of this collection with few probes into the property.
In this talk we describe a recently emerging line of work that attempts to unify the testing of such algebraic properties by their invariance. Specifically, we consider properties of functions mapping a large (but finite) field K to a small field F that are invariant under (the roughly K^2) affine transformations of the domain. In this talk we will give some motivation for studying this abstraction, as well as some of the results.
Based on works of/with Eli Ben-Sasson, Elena Grigorescu, Tali Kaufman, Shachar Lovett, Ghid Maatouk, Amir Shpilka.