AF: Small : Collaborative Research : A Theory of High Dimensional Property Testing

大规模数据集的出现需要设计和分析仅访问输入数据的一小部分的算法。该建议旨在进一步的数学研究，这些算法的次线性算法和性能测试的理论计算机科学的背景下。具体来说，重点是深入理解表示为高维函数的数据，这是许多优化问题中普遍存在的一种范式，以及如何使用小样本快速确定这些有用的属性。对这些问题的理解必然会导致更好，更快，更强大的数据分析算法。该建议涉及在调查人员各自的机构培训和指导研究生和本科生，特别关注妇女和少数民族学生。该提案的调查结果将不仅通过技术报告，而且通过人人都能访问的博客和视频向公众公布。研究人员有将理论理解转化为实际算法的记录，本提案将继续这一努力。离散的高维函数在科学中无处不在，理解和利用这些函数的性质是必要的。许多基本性质，如单调性，Lipschitz连续性，凸性和次模性，都是由这些函数的一阶，二阶或高阶导数的界定义的。本提案旨在理解导数有界属性测试背后的理论，特别是发现确定函数是否（近似）满足该类属性的最快算法。特别是，该提案旨在实现以下目标：（1）获得子模块性和离散凸性的快速测试仪，建立在一阶导数测试仪的研究人员以前的工作。(2)将结果从离散设置转换为连续设置，并获得凸度等属性的测试仪。(3)揭示几何概念之间的更多联系，如对偶性和等周性与导数测试算法，已经建议由以前的工作的调查人员。这个奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

The advent of massive data sets requires the design and analysis of algorithms accessing only a tiny portion of input data. This proposal aims to further the mathematical study of these algorithms in the context of sublinear algorithms and property testing within theoretical computer science. Specifically, the focus is an in-depth understanding of data represented as high dimensional functions, a paradigm prevalent in many optimization problems, and how useful properties of these can be quickly ascertained using small samples. An understanding of these issues foreseeably will lead to better, faster, and more robust algorithms for data analysis. The proposal involves training and mentoring graduate and undergraduate students at the investigators' respective institutions with special attention given to women and minority students. The findings of this proposal will be made accessible to public not only via technical reports but also via blogs and videos accessible to everyone. The investigators have a track record of converting theoretical understandings to practical algorithms, and this proposal will continue this effort. Discrete, high dimensional functions are ubiquitous in science, and it is imperative to understand and exploit properties of these functions. Many fundamental properties such as monotonicity, Lipschitz continuity, convexity and submodularity are defined by bounds on the first, second, or higher derivatives of these functions. This proposal aims to understand the theory behind derivative-bounded property testing, and in particular discover the fastest algorithms that determine whether a function (approximately) satisfies a property from this class. In particular, the proposal aims to achieve the following goals: (1) Obtain a fast tester of submodularity and discrete convexity, building on previous work of the investigators on first derivative testers. (2) Transfer results from discrete settings to continuous settings, and obtain testers for properties like convexity. (3) Uncover more connections between geometric concepts like duality and isoperimetry with derivative testing algorithms, as has been suggested by previous work of the investigators.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.