Invariance in Property Testing

属性测试的不变性

• 批准号: 0829672
• 负责人: Madhu Sudan
• 金额: $ 45万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0829672&HistoricalAwards=false
• 关键词: Invariance; 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.

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