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; 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.

该奖项研究布尔函数的结构 - 许多输出的输入的函数。该奖项的主要目标是研究各个投入对产出的影响，以及对输入载体的随机扰动的稳定性。对影响和稳定性的研究将用于获取用于从数据学习的新算法，并使用傅立叶扩展的概括分析马尔可夫链采样程序。它将与近似硬度理论的工具一起进一步使用，以表明对于某些组合优化问题，很难（甚至）（甚至）一个近似最佳的解决方案。该奖项的一个主要主题是获得有关高斯度量的几何形状的新结果，作为分析布尔函数稳定性的关键步骤。这遵循了不变性原则的一般哲学，该哲学认为，在某些情况下，高斯变量的位置和功能的功能，它们更易于分析，表现类似。该奖项将通过向纯数学，理论计算机科学及其应用之间的新联系来介绍新研究生的教育工作和指导。现代计算的关键特征是其二进制性质。该奖项将调查以以下问题为动机的二进制和其他计算模型：这些计算模型的稳健性如何？他们如何对数据进行分类？它们如何用来解决大型优化问题？该方法基于数​​学分析的深层工具的一部分，包括研究高维度中的几何问题。