AF: Small: Analysis of Boolean Functions

该奖项致力于布尔函数分析的新研究。 布尔函数（即，从n比特到1比特的映射）是计算机科学中最基本的研究对象之一：它们出现在密码学、纠错码、学习理论和电路设计等不同的领域。 研究布尔函数最有效的工具之一是考虑它们的傅里叶变换和相关的分析性质。 在过去的十年里，PI一直处于布尔函数分析研究的最前沿，并将通过对三个重要的未解决问题的攻击进一步发展理论和应用：1。傅立叶熵影响猜想关于如何“展开”布尔函数的傅立叶系数。 证明这一猜想将对理论学习产生重要影响。Aaronson-Ambainis猜想对低次布尔函数的影响。 这个猜想与理解量子计算的力量有直接的关系。关于可由低次多项式的符号计算的函数的Gotsman-Linial猜想。 布尔函数的分析在计算机科学中有着广泛的应用，它也通过在数学、统计物理和经济学中的应用而具有跨学科的应用。 PI将通过编写第一本关于布尔函数分析的教科书来进一步发展和传播该领域的影响。 这本教科书将在博客上分期免费发布。 这不仅将加强研究与教育之间的联系，还将促进计算机科学家（以及有抱负的计算机科学家）的学习，而无论其地位和地理位置如何。 最后，PI将继续通过为研究生和博士后研究人员提供咨询和指导，并通过广泛传播研究成果来产生更广泛的影响。

This award is dedicated to the new research on the analysis of Boolean functions. Boolean functions (i.e., mappings from n bits to 1 bit) are one of the most basic objects of study in computer science: they arise in areas as diverse as cryptography, error-correcting codes, learning theory, and circuit design. One of the most effective tools for studying Boolean functions is by considering their Fourier transform and related analytic properties. The PI has been at the forefront of research on analysis of Boolean functions over the last decade and will further develop theory and applications via an attack on three important unsolved problems:1. The Fourier Entropy-Influence Conjecture on how "spread out" the Fourier coefficients of a Boolean function can be. Proving this conjecture would have important consequences for learning theory.2. The Aaronson-Ambainis Conjecture on influences of low-degree Boolean functions. This conjecture has direct relevance to understanding the power of quantum computation.3. The Gotsman-Linial Conjecture on functions computable by the sign of a low-degree polynomial. This is a major problem in the field of concrete complexity.Analysis of Boolean functions has had broad application throughout computer science; it has also had interdisciplinary application through its use in mathematics, statistical physics, and economics. The PI will further develop and spread the impact of the area by writing the first textbook on analysis of Boolean functions. The textbook will be released freely, in installments on a blog. This will not only enhance the connection between research and education, it will foster learning for computer scientists (and aspiring computer scientists) regardless of status and geographic location. Finally, the PI will continue to make broader impact through advising and guiding graduate students and postdoctoral researchers, and through widely disseminating research results.