Boolean Functions: Influence, threshold and noise

  • Gil Kalai

    Hebrew University, Jerusalem, Israel
Boolean Functions: Influence, threshold and noise cover
Download Chapter PDF

A subscription is required to access this book chapter.

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 nn-dimensional discrete cube Ωn\Omega_n. Boolean functions are functions from Ωnto0,1\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 Ωn\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.