AF: Small: Boolean Functions: Inequalities, Structure, Algorithms & Hardness

AF：小：布尔函数：不等式、结构、算法

• 批准号: 1665252
• 负责人: Elchanan Mossel
• 金额: $ 37.08万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1665252&HistoricalAwards=false
• 关键词: AF; Small; Boolean; Functions; Inequalities

The award studies the structure of Boolean functions - functions of many inputs whose output is binary. The main goal of the award is to study the influence of individual inputs on the output, as well as the stability of the output to random perturbations applied to the vector of inputs. The study of influences and stability will be used to obtain new algorithms for learning from data and for analyzing markov-chain sampling procedures using generalizations of the Fourier expansion. It will be further used in conjunction with tools from the theory of hardness of approximation to show that for some combinatorial optimization problems it is computationally hard to find (even) an approximately optimal solution. A main theme of the award is to obtain new results on the geometry of the Gaussian measure as a key step for analyzing stability of Boolean functions. This follows the general philosophy of invariance principles which argue that in certain situations functions of bits and functions of Gaussian variables, which are easier to analyze, behave similarly. The award will support the educational efforts and mentoring of new graduate students by introducing to them new connections between pure mathematics, theoretical computer science and their applications.A key feature of modern computation is its binary nature. The award will investigate binary and other computational models motivated by the following questions: How robust are these computational models? How well can they classify data? How well can they be used to solve large optimization problems? The approach is based in parts on deep tools from mathematical analysis including the study of geometric problems in high dimensions.

该奖项研究的是布尔函数的结构，即输出为二进制的多输入函数。该奖项的主要目标是研究单个输入对输出的影响，以及对输入向量施加随机扰动时输出的稳定性。对影响和稳定性的研究将用于获得新的算法，用于从数据中学习，并使用傅里叶展开的推广来分析马尔可夫链抽样过程。它将进一步与来自近似硬度理论的工具结合使用，以表明对于某些组合优化问题，在计算上很难找到（甚至）近似最优解。该奖项的一个主要主题是在高斯测度的几何上获得新的结果，作为分析布尔函数稳定性的关键步骤。这遵循了不变性原理的一般哲学，该原理认为，在某些情况下，比特函数和高斯变量函数的行为相似，它们更容易分析。该奖项将通过向新研究生介绍纯数学、理论计算机科学及其应用之间的新联系，支持他们的教育工作和指导。现代计算的一个关键特征是它的二进制性质。该奖项将调查二进制和其他由以下问题驱动的计算模型：这些计算模型有多健壮？他们对数据的分类能力如何？它们在解决大型优化问题时的效果如何？该方法部分基于数学分析的深度工具，包括高维几何问题的研究。