ANALYSIS OF BOOLEAN FUNCTIONS Ryan O'Donnell Copyright @Ryan O'Donnell,2014. Published 2014 by Cambridge University Press. Cover illustration by A.A.Williams. Single paper or electronic copies for noncommercial personal use may be made without explicit permission from the author or publisher.All other rights reserved
ANALYSIS OF BOOLEAN FUNCTIONS Ryan O’Donnell Copyright © Ryan O’Donnell, 2014. Published 2014 by Cambridge University Press. Cover illustration by A. A. Williams. Single paper or electronic copies for noncommercial personal use may be made without explicit permission from the author or publisher. All other rights reserved
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
vi Contents $3.4.Learning theory 78 $3.5.Highlight:the Goldreich-Levin Algorithm 82 $3.6.Exercises and notes 85 Chapter 4.DNF formulas and small-depth circuits 93 $4.1.DNF formulas 93 $4.2.Tribes 96 $4.3.Random restrictions 98 $4.4.Hastad's Switching Lemma and the spectrum of DNFs 100 $4.5.Highlight:LMN's work on constant-depth circuits 103 $4.6.Exercises and notes 107 Chapter 5.Majority and threshold functions 113 $5.1.Linear threshold functions and polynomial threshold functions 113 $5.2.Majority,and the Central Limit Theorem 118 $5.3.The Fourier coefficients of Majority 121 $5.4.Degree-1 weight 124 $5.5.Highlight:Peres's Theorem and uniform noise stability 130 $5.6.Exercises and notes 134 Chapter 6.Pseudorandomness and F2-polynomials 143 $6.1.Notions of pseudorandomness 143 $6.2.F2-polynomials 148 $6.3.Constructions of various pseudorandom functions 151 $6.4.Applications in learning and testing 155 $6.5.Highlight:Fooling F2-polynomials 160 $6.6.Exercises and notes 163 Chapter 7.Property testing,PCPPs,and CSPs 173 $7.1.Dictator testing 173 $7.2.Probabilistically Checkable Proofs of Proximity 178 $7.3.CSPs and computational complexity 183 $7.4.Highlight:Hastad's hardness theorems 190 $7.5.Exercises and notes 195 Chapter 8.Generalized domains 207 $8.1.Fourier bases for product spaces 207 $8.2.Generalized Fourier formulas 211 Copyright@Ryan O'Donnell,2014
vi Contents §3.4. Learning theory 78 §3.5. Highlight: the Goldreich–Levin Algorithm 82 §3.6. Exercises and notes 85 Chapter 4. DNF formulas and small-depth circuits 93 §4.1. DNF formulas 93 §4.2. Tribes 96 §4.3. Random restrictions 98 §4.4. Håstad’s Switching Lemma and the spectrum of DNFs 100 §4.5. Highlight: LMN’s work on constant-depth circuits 103 §4.6. Exercises and notes 107 Chapter 5. Majority and threshold functions 113 §5.1. Linear threshold functions and polynomial threshold functions 113 §5.2. Majority, and the Central Limit Theorem 118 §5.3. The Fourier coefficients of Majority 121 §5.4. Degree-1 weight 124 §5.5. Highlight: Peres’s Theorem and uniform noise stability 130 §5.6. Exercises and notes 134 Chapter 6. Pseudorandomness and ❋2-polynomials 143 §6.1. Notions of pseudorandomness 143 §6.2. ❋2-polynomials 148 §6.3. Constructions of various pseudorandom functions 151 §6.4. Applications in learning and testing 155 §6.5. Highlight: Fooling ❋2-polynomials 160 §6.6. Exercises and notes 163 Chapter 7. Property testing, PCPPs, and CSPs 173 §7.1. Dictator testing 173 §7.2. Probabilistically Checkable Proofs of Proximity 178 §7.3. CSPs and computational complexity 183 §7.4. Highlight: Håstad’s hardness theorems 190 §7.5. Exercises and notes 195 Chapter 8. Generalized domains 207 §8.1. Fourier bases for product spaces 207 §8.2. Generalized Fourier formulas 211 Copyright © Ryan O’Donnell, 2014
Contents vii $8.3.Orthogonal decomposition 216 $8.4.p-biased analysis 220 $8.5.Abelian groups 227 $8.6.Highlight:Randomized decision tree complexity 229 $8.7.Exercises and notes 235 Chapter 9.Basics of hypercontractivity 247 $9.1.Low-degree polynomials are reasonable 248 $9.2.Small subsets of the hypercube are noise-sensitive 252 $9.3.(2,g)-and (p,2)-hypercontractivity for a single bit 256 $9.4.Two-function hypercontractivity and induction 259 $9.5.Applications of hypercontractivity 262 $9.6.Highlight:The Kahn-Kalai-Linial Theorem 265 $9.7.Exercises and notes 270 Chapter 10.Advanced hypercontractivity 283 $10.1.The Hypercontractivity Theorem for uniform t1 bits 283 $10.2.Hypercontractivity of general random variables 287 $10.3.Applications of general hypercontractivity 292 §10.4. More on randomization/symmetrization 296 $10.5.Highlight:General sharp threshold theorems 304 $10.6.Exercises and notes 311 Chapter 11.Gaussian space and Invariance Principles 325 $11.1.Gaussian space and the Gaussian noise operator 326 $11.2.Hermite polynomials 334 $11.3.Borell's Isoperimetric Theorem 338 $11.4.Gaussian surface area and Bobkov's Inequality 341 $11.5.The Berry-Esseen Theorem 348 $11.6.The Invariance Principle 355 $11.7.Highlight:Majority Is Stablest Theorem 362 $11.8.Exercises and notes 368 Some tips 387 Bibliography 389 Index 4红1 Revision history 419 Copyright@Ryan O'Donnell,2014
Contents vii §8.3. Orthogonal decomposition 216 §8.4. p-biased analysis 220 §8.5. Abelian groups 227 §8.6. Highlight: Randomized decision tree complexity 229 §8.7. Exercises and notes 235 Chapter 9. Basics of hypercontractivity 247 §9.1. Low-degree polynomials are reasonable 248 §9.2. Small subsets of the hypercube are noise-sensitive 252 §9.3. (2, q)- and (p,2)-hypercontractivity for a single bit 256 §9.4. Two-function hypercontractivity and induction 259 §9.5. Applications of hypercontractivity 262 §9.6. Highlight: The Kahn–Kalai–Linial Theorem 265 §9.7. Exercises and notes 270 Chapter 10. Advanced hypercontractivity 283 §10.1. The Hypercontractivity Theorem for uniform ±1 bits 283 §10.2. Hypercontractivity of general random variables 287 §10.3. Applications of general hypercontractivity 292 §10.4. More on randomization/symmetrization 296 §10.5. Highlight: General sharp threshold theorems 304 §10.6. Exercises and notes 311 Chapter 11. Gaussian space and Invariance Principles 325 §11.1. Gaussian space and the Gaussian noise operator 326 §11.2. Hermite polynomials 334 §11.3. Borell’s Isoperimetric Theorem 338 §11.4. Gaussian surface area and Bobkov’s Inequality 341 §11.5. The Berry–Esseen Theorem 348 §11.6. The Invariance Principle 355 §11.7. Highlight: Majority Is Stablest Theorem 362 §11.8. Exercises and notes 368 Some tips 387 Bibliography 389 Index 411 Revision history 419 Copyright © Ryan O’Donnell, 2014
Preface The subject of this textbook is the analysis of Boolean functions.Roughly speaking,this refers to studying Boolean functions f:(0,1)"-(0,1)via their Fourier expansion and other analytic means.Boolean functions are perhaps the most basic object of study in theoretical computer science,and Fourier analysis has become an indispensable tool in the field.The topic has also played a key role in several other areas of mathematics,from combinatorics, random graph theory,and statistical physics,to Gaussian geometry,met- ric/Banach spaces,and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide(though far from exhaustive)overview of its applications.Each chapter ends with a"highlight"showing the power of analysis of Boolean functions in different subject areas:property testing,social choice,cryptog- raphy,circuit complexity,learning theory,pseudorandomness,hardness of approximation,concrete complexity,and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course.The author has twice taught such a course at Carnegie Mellon University,attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs,and researchers in adjacent fields.In both years most of Chapters 1- 5 and 7 were covered,along with parts of Chapters 6,8,9,and 11,and some additional material on additive combinatorics.Nearly 500 exercises are provided at the ends of the book's chapters. Copyright Ryan O'Donnell,2014
Preface The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions f : {0,1} n → {0,1} via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a “highlight” showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1– 5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the book’s chapters. ix Copyright © Ryan O’Donnell, 2014