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

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

• 批准号: 1813053
• 负责人: Deeparnab Chakrabarty
• 金额: $ 26.5万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813053&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.

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

项目成果

On a Decentralized (Δ+1)-Graph Coloring Algorithm

• DOI: 10.1137/1.9781611976014.13
• 发表时间: 2020-01
• 作者: Deeparnab Chakrabarty;P. D. Supinski

Adaptive Boolean Monotonicity Testing in Total Influence Time

总影响时间的自适应布尔单调性测试

• 发表时间: 2019
• 期刊: ITCS 2019
• 作者: Chakrabarty, Deeparnab;Seshadhri, C.
• 通讯作者: Seshadhri, C.

Robust k-Center with Two Types of Radii

具有两种半径的稳健 k 中心

• DOI: 10.1007/978-3-030-73879-2_19
• 发表时间: 2021
• 期刊: Integer Programming and Combinatorial Optimization
• 作者: Chakrabarty, D;Negahbani, M
• 通讯作者: Negahbani, M

Graph Connectivity and Single Element Recovery via Linear and OR Queries

• DOI: 10.4230/lipics.esa.2021.7
• 发表时间: 2020-07
• 作者: Sepehr Assadi;Deeparnab Chakrabarty;S. Khanna

Revisiting Priority k-Center: Fairness and Outliers

• DOI: 10.4230/lipics.icalp.2021.21
• 发表时间: 2021-03
• 期刊: ArXiv
• 作者: Tanvi Bajpai;Deeparnab Chakrabarty;C. Chekuri;Maryam Negahbani