Two Decades of Property Testing

Speaker: 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

Public: Yes

Location: G449 (Patil/Kiva)

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Deborah Goodwin Email at Tuesday, October 07, 2014 at 8:31 AM.