Collaborative Research: AF: Medium: Continuous Concrete Complexity

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

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.