Two Decades of Property Testing

Madhu Sudan (Harvard)

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 satifies 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.