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

大量数据集的出现要求设计和分析算法，只访问输入数据的一小部分。本提案旨在进一步在次线性算法和理论计算机科学中性能测试的背景下对这些算法进行数学研究。具体来说，重点是深入理解以高维函数表示的数据，这是许多优化问题中普遍存在的范式，以及如何使用小样本快速确定这些有用的属性。可以预见地理解这些问题将导致更好、更快、更健壮的数据分析算法。该建议涉及在调查人员各自的机构培训和指导研究生和本科生，并特别注意妇女和少数民族学生。这项提案的研究结果不仅将通过技术报告，还将通过博客和视频向公众开放。研究人员有将理论理解转化为实际算法的记录，本提案将继续这一努力。离散的高维函数在科学中无处不在，理解和利用这些函数的性质是势在必行的。许多基本性质，如单调性、利普希茨连续性、凸性和亚模性，是由这些函数的一阶、二阶或更高阶导数的界来定义的。本提案旨在理解导数有界性质测试背后的理论，特别是发现确定函数是否（近似）满足该类性质的最快算法。具体而言，该方案旨在实现以下目标：(1)在一阶导数测试器的基础上，获得一种快速的子模块化和离散凸性测试器。(2)将离散设置的结果传递到连续设置，获得凹凸性等属性的测试器。(3)揭示几何概念之间的更多联系，如对偶性和等距导数测试算法，正如研究者之前的工作所建议的那样。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.