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.
