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

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

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.