Two Decades of Property Testing
Madhu Sudan, Principal Researcher, Microsoft; Adjunct Professor, EECS, MIT
Date: Tuesday, December 09, 2014
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 4:00 PM
Location: G449 (Patil/Kiva)
Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan
Contact: Deborah Lehto, 617.324.7303, email@example.com
Speaker URL: None
TALK: Madhu Sudan: 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 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. 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.
Created by Deborah Goodwin at Tuesday, October 07, 2014 at 8:31 AM.