Boolean functions: influence, threshold and noise (Q1620841)

Summary: 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. For the entire collection see [Zbl 1396.00017].