Property testing, with a focus on invariances
Arnab Bhattacharyya, Massachusetts Institute of Technology
We survey the field of "property testing". Property testing considers the task of testing super-efficiently whether a given object satisfies some desirable property or is far from satisfying this property. The tester is an algorithm that has query access to the input object; this algorithm is necessarily randomized if its running time is very small compared to the size of the object. We wish to design testers that can provably distinguish objects having the property from object far from having the property using a really small number of queries. In fact, in many cases, we can show that the number of queries needed can be taken to be independent of the size of the object! We call such properties "testable". It is a longstanding open question in the area to characterize testable properties. We survey the progress here. While a general characterization still remains seemingly far in the future, one can complete the characterization if restricted to properties of graphs. I, along with several co-authors, have also made progress towards understanding the testability of algebraic properties, thus unifying several "special case" analyses done previously. I also describe a possible approach towards a characterization of testable properties which are symmetric under any given group of invariances. The work surveyed is joint with several sets of collaborators, all of whom will be named during the talk.
Abstract Author(s): Arnab Bhattacharyya