Invariance in Property Testing

这个项目在性能测试中开创了新的、统一的方向。属性测试是算法研究的一个领域，它试图通过在很少的地方对数据进行概率抽样来发现数据的全局属性。“最古老”的财产测试可能是利用民意调查来预测即将到来的选举结果。现代研究的范围扩展属性测试更丰富的类的属性包括线性测试(“数据本质上是线性的对一些参数”)、multilinearity low-degreeness,着色性能(“数据描述一个图小彩色数字”)等这个项目的目标是阐明一个问题:是什么让一些性能测试的效率,我们不必看整个数据为了测试吗?该项目的基本论点是，对于有趣的属性，可测试性应该与属性所显示的“不变性”有关：即，如果将数据视为从某些输入到某些输出的函数，那么“不变性”是由输入空间的一组（一组）排列给出的，在该属性保持不变的情况下。该项目探索了各种潜在的不变性，并研究了显示这种不变性的{\em每}属性是可测试的条件。该项目的更广泛影响是通过描述可以通过采样小块来分析大量数据的设置，找到应对许多计算机面临的数据爆炸问题的方法。

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.