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.

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

项目成果

Testing Convex Truncation

测试凸截断

• 发表时间: 2023
• 期刊: Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms
• 作者: De, Anindya;Nadimpali, Shivam;Servedio, Rocco A.
• 通讯作者: Servedio, Rocco A.