February 26th – March 4th, 2012 | Ryan O'Donnell, Per Austrin
This document presents a series of lectures on the analysis of boolean functions, focusing on topics such as linearity testing, noise stability, and the hardness of approximation. The content includes detailed discussions on Fourier expansions, noise stability, and the relationship between boolean functions and voting systems. Key concepts include the Fourier transform of boolean functions, noise stability, and the application of these concepts to problems like Arrow's theorem. The lectures also explore the connection between boolean functions and the noisy hypercube graph, as well as the use of the Berry-Esséen theorem in analyzing the convergence of random variables. The material covers various theorems and proofs, including the Blum-Luby-Rubinfeld linearity test, the analysis of influence and total influence of boolean functions, and the implications of noise stability for voting systems. The content is structured into several sections, each addressing different aspects of boolean function analysis and its applications.This document presents a series of lectures on the analysis of boolean functions, focusing on topics such as linearity testing, noise stability, and the hardness of approximation. The content includes detailed discussions on Fourier expansions, noise stability, and the relationship between boolean functions and voting systems. Key concepts include the Fourier transform of boolean functions, noise stability, and the application of these concepts to problems like Arrow's theorem. The lectures also explore the connection between boolean functions and the noisy hypercube graph, as well as the use of the Berry-Esséen theorem in analyzing the convergence of random variables. The material covers various theorems and proofs, including the Blum-Luby-Rubinfeld linearity test, the analysis of influence and total influence of boolean functions, and the implications of noise stability for voting systems. The content is structured into several sections, each addressing different aspects of boolean function analysis and its applications.