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.