Boolean Functions: Influence, threshold and noise

Abstract

This lecture studies the analysis of Boolean functions and present a few ideas, results, proofs, and problems. We start with the wider picture of expansion in graphs and then concentrate on the graph of the $n$-dimensional discrete cube ${\Omega }_n$. Boolean functions are functions from ${\Omega }_{n}to0,1$. We consider the notion of the influence of variables on Boolean functions. The influence of a variable on a Boolean function is the probability that changing the value of the variable changes the value of the function. We then consider Fourier analysis of real functions on ${\Omega }_n$ and some applications of Fourier methods. We go on to discuss connections with sharp threshold phenomena, percolation, random graphs, extremal combinatorics, correlation inequalities, and more.