This project initiates new, unifying directions in Property Testing. Property Testing is the area of algorithmic research that attempts to discover global properties of data by by sampling the data probabilistically in very few places. The ``oldest'' property test might be the use of polling to predict the outcome of an upcoming election. Modern research has extended the scope of property tests to a much richer class of properties including tests of linearity (``is the data essentially linear with respect to some parameters"), multilinearity, low-degreeness, colorability (``is the data describing a graph with small chromatic number") etc.
The goal of this project is to shed light on the question: What makes some properties testable so efficiently, that we do not have to look at the entire data in order to test for it? The thesis underlying the project is that for interesting properties, testability ought to be related to the ``invariances" shown by the property: i.e., if the data is viewed as a function from some input to some output, then the ``invariances" are given by a set (a group) of permutations of the input space under which the property remains unchanged. The project explores a variety of potential invariances to consider and studies conditions under which {em every} property exhibiting such invariance is testable.
The broader impact of the project is to find ways of coping with the data explosion problem faced by many computers, by describing settings where massive data may be analyzed by sampling small pieces.
