Boolean Functions: Influence, threshold and noise
Gil Kalai · EMS Press eBooks · 2018
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 to {0,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.