Seminar: October 18

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.