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 -dimensional discrete cube . Boolean functions are functions from . 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 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.