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

AF：小：协作研究：高维性能测试理论

基本信息

批准号：
1813165
负责人：
C Sesh Seshadhri
金额：
$ 23万
依托单位：
University of California-Santa Cruz
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-07-01 至 2022-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813165&HistoricalAwards=false
关键词：
AF Small Collaborative Research Theory

项目摘要

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.

大规模数据集的出现需要设计和分析算法仅访问一小部分输入数据。该建议旨在在理论计算机科学中的sublrinear算法和属性测试的背景下进一步对这些算法进行数学研究。具体而言，焦点是对表示为高维函数的数据的深入理解，在许多优化问题中普遍存在的范式，以及如何使用小样本快速确定这些数据的有用属性。对这些问题的理解将导致数据分析的更好，更快，更强大的算法。该提案涉及调查人员各自的机构的培训和指导研究生和本科生，并特别关注妇女和少数民族学生。该提案的发现将不仅可以通过技术报告，而且还可以通过博客和所有人访问的视频来访问。研究人员有将理论理解转换为实际算法的记录，该提议将继续这一努力。离散的高维函数在科学中无处不在，必须理解和利用这些功能的性质。许多基本特性，例如单调性，Lipschitz的连续性，凸度和次二次性，这些功能由这些功能的第一，第二或更高衍生物的边界定义。该建议旨在了解衍生物结合的属性测试背后的理论，尤其是发现确定功能（大约）是否满足该类属性的最快算法。特别是，该提案旨在实现以下目标：（1）获得基于研究人员先前在第一派生测试人员的工作的基础，以基于次要性和离散凸度的快速测试仪。（2）将离散设置的结果转移到连续设置，并获取诸如凸度之类的属性的测试者。（3）正如研究人员先前的工作所建议的那样，发现二元性和等值算法等几何概念与等值算法之间的更多联系。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力和更广泛影响的评估来通过评估来支持的，这是值得的。