Contents Preface 这 List of Notation xiii Chapter 1.Boolean functions and the Fourier expansion 19 $1.1.On analysis of Boolean functions 19 $1.2.The"Fourier expansion":functions as multilinear polynomials 20 $1.3.The orthonormal basis of parity functions 23 $1.4.Basic Fourier formulas 25 $1.5.Probability densities and convolution 28 $1.6.Highlight:Almost linear functions and the BLR Test 31 $1.7.Exercises and notes 33 Chapter 2.Basic concepts and social choice 43 $2.1.Social choice functions 43 $2.2.Influences and derivatives 46 $2.3.Total influence 49 $2.4.Noise stability 53 $2.5.Highlight:Arrow's Theorem 57 $2.6.Exercises and notes 61 Chapter 3.Spectral structure and learning 69 $3.1.Low-degree spectral concentration 69 $3.2.Subspaces and decision trees 71 $3.3.Restrictions 74 Copyright@Ryan O'Donnell,2014.Contents Preface ix List of Notation xiii Chapter 1. Boolean functions and the Fourier expansion 19 §1.1. On analysis of Boolean functions 19 §1.2. The “Fourier expansion”: functions as multilinear polynomials 20 §1.3. The orthonormal basis of parity functions 23 §1.4. Basic Fourier formulas 25 §1.5. Probability densities and convolution 28 §1.6. Highlight: Almost linear functions and the BLR Test 31 §1.7. Exercises and notes 33 Chapter 2. Basic concepts and social choice 43 §2.1. Social choice functions 43 §2.2. Influences and derivatives 46 §2.3. Total influence 49 §2.4. Noise stability 53 §2.5. Highlight: Arrow’s Theorem 57 §2.6. Exercises and notes 61 Chapter 3. Spectral structure and learning 69 §3.1. Low-degree spectral concentration 69 §3.2. Subspaces and decision trees 71 §3.3. Restrictions 74 v Copyright © Ryan O’Donnell, 2014