Boolean Functions: Inequalities, Structure, Algorithms and Hardness

Research 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.