Two Decades of Property Testing

ABSTRACT:  Property Testing studies the design and analysis of algorithms that Test if some (massive) data satisfies some global Property without looking at all the data, or inferring the parameters that explain how the data satisfies the property. It was initiated by accidental discoveries, by Blum, Luby and Rubinfeld, and by Babai, Fortnow and Lund,  showing that some complex properties could be tested remarkably efficiently. In the nearly quarter century since these discoveries, the scope of Property Testing has expanded broadly - it covers properties of algebraic, graph-theoretic, statistical, and functional nature; and the resulting techniques have connected the field to combinatorics, additive number theory, harmonic analysis, algebraic geometry, while having applications in complexity theory, combinatorial optimization and even extremal graph theory.

In this talk I will look back at some of this history attempting to describe some of the diversity of the results and impact; and try to present a personal perspective, via "Invariance", that explains some of the reason for the diversity, and tries to extract some coherent picture among this diversity. Time permitting, I will describe our attempts to use ``affine-invariance'' to explain testability of algebraic properties which has resulted in unification of known results, some unexpected strengthens, counterexamples to several conjectures and new locally testable and decodable codes.