Collaborative Research: AF: Medium: Continuous Concrete Complexity

合作研究：AF：中：连续混凝土复杂性

• 批准号: 2211238
• 负责人: Rocco Servedio
• 金额: $ 60万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2211238&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Continuous

In theoretical computer science the well-established field of concrete complexity studies structural properties of "Boolean functions", which are decision rules that amalgamate a list of responses to yes/no questions to produce a single yes/no output value. Boolean functions are central to many branches of computer science, including the study of machine-learning algorithms (where a major goal is to efficiently infer Boolean functions based on their input-output performance) as well as hyperefficient "property testing" algorithms that inspect only a tiny portion of a massive data set in order to estimate some global property of the data. In a parallel, but to-date largely disconnected, line of research, mathematicians have expended great effort towards understanding structural properties of various types of geometric sets in high-dimensional continuous space. Such sets can also be viewed as "decision rules", but ones that amalgamate a list of continuous numerical values, rather than discrete yes/no answers, in order to produce a yes/no value (which indicates whether or not the input point described by the numerical values belongs to the set). Viewed from this very high-level perspective these two lines of research have similar broad goals, but the techniques they use are quite different, and the two fields have mostly considered distinct types of questions and mathematical objects.In this project the investigators will work to establish and deepen connections between the two settings --- discrete and continuous --- described above. The driving force behind this project is an analogy, developed by the investigators in a sequence of recent works, between Boolean functions that are monotone non-decreasing and high-dimensional sets that are convex. This perspective has already led to a number of surprising new results and suggests a broad range of new notions and questions as well as methods of proof. Building on their preliminary work, the investigators will work to establish new structural results for high-dimensional geometric sets (focusing in particular on convex sets in continuous high-dimensional spaces that are endowed with the Gaussian distribution) that are inspired by analogous structural results that have been established in concrete complexity for Boolean functions. As mentioned above, the structural results obtained to date in concrete complexity for discrete domains have proved very useful for computer science applications such as computational learning, property testing, and derandomization; the investigators will work to establish similar applications in learning, testing, and derandomization in the continuous setting. The investigators will also develop the connection between the discrete and continuous settings in the other direction, by working to apply some of the powerful methods of high-dimensional convex geometry to obtain new structural and algorithmic results in the discrete Boolean setting. Finally, another important goal of the project is to train graduate students through the process of research collaboration and dissemination, with a particular goal of building expertise that spans both the topics of high-dimensional convex geometry and discrete Boolean concrete complexity.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.

在理论计算机科学中，成熟的具体复杂性领域研究“布尔函数”的结构特性，这些决策规则合并对是/否问题的回答列表以产生单个是/否输出值。布尔函数是计算机科学许多分支的核心，包括机器学习算法的研究（其主要目标是根据布尔函数的输入输出性能有效地推断布尔函数）以及仅检查的超高效“属性测试”算法大量数据集的一小部分，以便估计数据的某些全局属性。在并行但迄今为止基本上互不相关的研究领域中，数学家付出了巨大的努力来理解高维连续空间中各种类型几何集的结构特性。这样的集合也可以被视为“决策规则”，但是这些集合合并了一系列连续数值，而不是离散的是/否答案，以便产生是/否值（这表明输入点是否描述了由属于该集合的数值）。从这个非常高层次的角度来看，这两个研究方向具有相似的广泛目标，但它们使用的技术却截然不同，并且这两个领域主要考虑不同类型的问题和数学对象。在这个项目中，研究人员将致力于建立并加深上述两种设置（离散和连续）之间的联系。该项目背后的驱动力是研究人员在最近的一系列工作中提出的一种类比，该类比是单调非递减的布尔函数和凸的高维集合之间的类比。这种观点已经带来了许多令人惊讶的新结果，并提出了广泛的新概念、新问题以及证明方法。在前期工作的基础上，研究人员将致力于为高维几何集（特别关注赋予高斯分布的连续高维空间中的凸集）建立新的结构结果，这些结果受到类似结构结果的启发，已经建立了布尔函数的具体复杂性。 如上所述，迄今为止在离散域的具体复杂性方面获得的结构结果已被证明对于计算学习、属性测试和去随机化等计算机科学应用非常有用；研究人员将致力于在连续环境中的学习、测试和去随机化方面建立类似的应用程序。研究人员还将在另一个方向上发展离散和连续设置之间的联系，通过努力应用高维凸几何的一些强大方法，在离散布尔设置中获得新的结构和算法结果。最后，该项目的另一个重要目标是通过研究合作和传播过程来培训研究生，其具体目标是建立涵盖高维凸几何和离散布尔具体复杂性主题的专业知识。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Testing Convex Truncation

测试凸截断

• 发表时间: 2023-01
• 期刊: Proceedings of the annual ACMSIAM Symposium on Discrete Algorithms
• 作者: De, Anindya;Nadimpalli, Shivam;Servedio, Rocco
• 通讯作者: Servedio, Rocco