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.