Techniques for Analysis of Boolean Functions

Abstract

We discuss techniques for Fourier analysis of Boolean functions. After an introduction to Boolean functions and their Fourier expansions, we discuss perhaps the simplest complexity measures of Boolean functions { sensitivity and influence. We turn to the question of nding restrictions on the Fourier coe cients of a Boolean function and derive an identity. Finally, we discuss the entropy-influence conjecture with a focus on useful generalizations of the problem, including generalizations of entropy and probability distribution. We propose a generalization of the Fourier basis using rotation matrices and derive an analogue of the Margulis-Russo Formula.