Invariance in Property Testing

该项目在性能测试方面开创了新的、统一的方向。属性测试是算法研究的领域，它试图通过在极少的地方对数据进行概率抽样来发现数据的全局属性。“最古老的”属性测试可能是使用民调来预测即将到来的选举的结果。现代研究已经将性能测试的范围扩展到更丰富的属性类别，包括线性测试(数据相对于某些参数本质上是线性的)、多线性测试、低度数测试、可着色性测试(数据描述的是小色数的图形)等。这个项目的目标是阐明这样一个问题：是什么使一些属性的测试如此有效，以至于我们不必为了测试它而查看整个数据？该项目的基本论点是，对于有趣的属性，可测试性应该与属性所显示的“不变性”相关：即，如果数据被视为从某一输入到某一输出的函数，则该“不变性”由输入空间的一组排列给出，在该排列下，该属性保持不变。该项目探索了要考虑的各种潜在不变性，并研究了具有这种不变性的性质是可测试的条件。该项目更广泛的影响是找到应对许多计算机面临的数据爆炸问题的方法，方法是描述通过对小块数据进行采样来分析海量数据的环境。

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.