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
Preface Additional material related to the book can be found at its website: http://analysisofbooleanfunctions.org This includes complete lecture notes from the author's 2007 course,complete lecture videos from the author's 2012 course,blog updates related to analysis of Boolean functions,an electronic draft of the book,and errata.The author would like to encourage readers to post any typos,bugs,clarification requests, and suggestions to this website. Acknowledgments My foremost acknowledgment is to all of the people who have taught me analysis of Boolean functions,especially Guy Kindler and Elchanan Mossel. I also learned a tremendous amount from my advisor Madhu Sudan,and my coauthors and colleagues Per Austrin,Eric Blais,Nader Bshouty,Ilias Di- akonikolas,Irit Dinur,Uri Feige,Ehud Friedgut,Parikshit Gopalan,Venkat Guruswami,Johan Hastad,Gil Kalai,Daniel Kane,Subhash Khot,Adam Klivans,James Lee,Assaf Naor,Joe Neeman,Krzysztof Oleszkiewicz,Yuval Peres,Oded Regev,Mike Saks,Oded Schramm,Rocco Servedio,Amir Shpilka, Jeff Steif,Benny Sudakov,Li-Yang Tan,Avi Wigderson,Karl Wimmer,John Wright,Yi Wu,Yuan Zhou,and many others.Ideas from all of them have strongly informed this book. Many thanks to my PhD students who suffered from my inattention dur- ing the completion of this book:Eric Blais,Yuan Zhou,John Wright,and David Witmer.I'd also like to thank the students who took my 2007 and 2012 courses on analysis of Boolean functions;special thanks to Deepak Bal,Carol Wang,and Patrick Xia for their very helpful course writing projects. Thanks to my editor Lauren Cowles for her patience and encouragement, to the copyediting team of David Anderson and Rishi Gupta,and to Cam- bridge University Press for welcoming the free online publication of this book. Thanks also to Amanda Williams for the use of the cover image on the book's website. I'm very grateful to all of the readers of the blog serialization who sug- gested improvements and pointed out mistakes in the original draft of this work:Amirali Abdullah,Stefan Alders,anon,Arda Antikacioglu,Albert At- serias,Per Austrin,Deepak Bal,Paul Beame,Tim Black,Ravi Boppana, Clement Canonne,Sankardeep Chakraborty,Bireswar Das,Andrew Drucker, Kirill Elagin,John Engbers,Diodato Ferraioli,Magnus Find,Michael Forbes, Matt Franklin,David Gajser,David Garcia Soriano,Dmitry Gavinsky,Daniele Gewurz,Mrinalkanti Ghosh,Sivakanth Gopi,Tom Gur,Zachary Hamaker, Copyright@Ryan O'Donnell,2014
x Preface Additional material related to the book can be found at its website: ❤tt♣✿✴✴❛♥❛❧②s✐s♦❢❜♦♦❧❡❛♥❢✉♥❝t✐♦♥s✳♦r❣ This includes complete lecture notes from the author’s 2007 course, complete lecture videos from the author’s 2012 course, blog updates related to analysis of Boolean functions, an electronic draft of the book, and errata. The author would like to encourage readers to post any typos, bugs, clarification requests, and suggestions to this website. Acknowledgments My foremost acknowledgment is to all of the people who have taught me analysis of Boolean functions, especially Guy Kindler and Elchanan Mossel. I also learned a tremendous amount from my advisor Madhu Sudan, and my coauthors and colleagues Per Austrin, Eric Blais, Nader Bshouty, Ilias Diakonikolas, Irit Dinur, Uri Feige, Ehud Friedgut, Parikshit Gopalan, Venkat Guruswami, Johan Håstad, Gil Kalai, Daniel Kane, Subhash Khot, Adam Klivans, James Lee, Assaf Naor, Joe Neeman, Krzysztof Oleszkiewicz, Yuval Peres, Oded Regev, Mike Saks, Oded Schramm, Rocco Servedio, Amir Shpilka, Jeff Steif, Benny Sudakov, Li-Yang Tan, Avi Wigderson, Karl Wimmer, John Wright, Yi Wu, Yuan Zhou, and many others. Ideas from all of them have strongly informed this book. Many thanks to my PhD students who suffered from my inattention during the completion of this book: Eric Blais, Yuan Zhou, John Wright, and David Witmer. I’d also like to thank the students who took my 2007 and 2012 courses on analysis of Boolean functions; special thanks to Deepak Bal, Carol Wang, and Patrick Xia for their very helpful course writing projects. Thanks to my editor Lauren Cowles for her patience and encouragement, to the copyediting team of David Anderson and Rishi Gupta, and to Cambridge University Press for welcoming the free online publication of this book. Thanks also to Amanda Williams for the use of the cover image on the book’s website. I’m very grateful to all of the readers of the blog serialization who suggested improvements and pointed out mistakes in the original draft of this work: Amirali Abdullah, Stefan Alders, anon, Arda Antikacıoglu, Albert At- ˘ serias, Per Austrin, Deepak Bal, Paul Beame, Tim Black, Ravi Boppana, Clément Canonne, Sankardeep Chakraborty, Bireswar Das, Andrew Drucker, Kirill Elagin, John Engbers, Diodato Ferraioli, Magnus Find, Michael Forbes, Matt Franklin, David Gajser, David García Soriano, Dmitry Gavinsky, Daniele Gewurz, Mrinalkanti Ghosh, Sivakanth Gopi, Tom Gur, Zachary Hamaker, Copyright © Ryan O’Donnell, 2014
Preface xi Prahladh Harsha,Justin Hilyard,Dmitry Itsykson,Hamidreza Jahanjou, Mitchell Johnston,Gautam Kamath,Shiva Kaul,Brian Kell,Pravesh Kothari, Chin Ho Lee,Euiwoong Lee,Holden Lee,Jerry Li,Noam Lifshitz,Tengyu Ma, Mladen Miksa,Aleksandar Nikolov,David Pritchard,Swagato Sanyal,Pranav Senthilnathan,Igor Shinkar,Lior Silberman,Marla Slusky,Dmitry Sokolov, Aravind Srinivasan,Avishay Tal,Li-Yang Tan,Roei Tell,Suresh Venkata- subramanian,Marc Vinyals,Emanuele Viola,Poorvi Vora,Amos Waterland, Karl Wimmer,Chung Hoi Wong,Xi Wu,Yi Wu,Mingji Xia,Yuichi Yoshida, Shengyu Zhang,and Yu Zhao.Special thanks in this group to Matt Franklin and Li-Yang Tan;extra-special thanks in this group to Noam Lifshitz. I'm grateful to Denis Therien for inviting me to lecture at the Barbados Complexity Workshop,to Cynthia Dwork and the STOC 2008 PC for inviting me to give a tutorial,and to the Simons Foundation who arranged for me to co-organize a symposium together with Elchanan Mossel and Krzysztof Oleskiewicz,all on the topic of analysis of Boolean functions.These opportu- nities greatly helped me to crystallize my thoughts on the topic. I worked on this book while visiting the Institute for Advanced Study in 2010-2011(supported by the Von Neumann Fellowship and in part by NSF grants DMS-0835373 and CCF-0832797);I'm very grateful to them for having me and for the wonderful working environment they provided.The remain- der of the work on this book was done at Carnegie Mellon;I'm of course very thankful to my colleagues there and to the Department of Computer Science. "Reasonable"random variables were named after the department's "Reason- able Person Principle".I was also supported in this book-writing endeavor by the National Science Foundation,specifically grants CCF-0747250 and CCF-1116594.As usual:"This material is based upon work supported by the National Science Foundation under grant numbers listed above.Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF)." Finally,I'd like to thank all of my colleagues,friends,and relatives who encouraged me to write and to finish the book,Zeynep most of all. -Ryan O'Donnell Pittsburgh October 2013 Copyright Ryan O'Donnell,2014
Preface xi Prahladh Harsha, Justin Hilyard, Dmitry Itsykson, Hamidreza Jahanjou, Mitchell Johnston, Gautam Kamath, Shiva Kaul, Brian Kell, Pravesh Kothari, Chin Ho Lee, Euiwoong Lee, Holden Lee, Jerry Li, Noam Lifshitz, Tengyu Ma, Mladen Mikša, Aleksandar Nikolov, David Pritchard, Swagato Sanyal, Pranav Senthilnathan, Igor Shinkar, Lior Silberman, Marla Slusky, Dmitry Sokolov, Aravind Srinivasan, Avishay Tal, Li-Yang Tan, Roei Tell, Suresh Venkatasubramanian, Marc Vinyals, Emanuele Viola, Poorvi Vora, Amos Waterland, Karl Wimmer, Chung Hoi Wong, Xi Wu, Yi Wu, Mingji Xia, Yuichi Yoshida, Shengyu Zhang, and Yu Zhao. Special thanks in this group to Matt Franklin and Li-Yang Tan; extra-special thanks in this group to Noam Lifshitz. I’m grateful to Denis Thérien for inviting me to lecture at the Barbados Complexity Workshop, to Cynthia Dwork and the STOC 2008 PC for inviting me to give a tutorial, and to the Simons Foundation who arranged for me to co-organize a symposium together with Elchanan Mossel and Krzysztof Oleskiewicz, all on the topic of analysis of Boolean functions. These opportunities greatly helped me to crystallize my thoughts on the topic. I worked on this book while visiting the Institute for Advanced Study in 2010–2011 (supported by the Von Neumann Fellowship and in part by NSF grants DMS-0835373 and CCF-0832797); I’m very grateful to them for having me and for the wonderful working environment they provided. The remainder of the work on this book was done at Carnegie Mellon; I’m of course very thankful to my colleagues there and to the Department of Computer Science. “Reasonable” random variables were named after the department’s “Reasonable Person Principle”. I was also supported in this book-writing endeavor by the National Science Foundation, specifically grants CCF-0747250 and CCF-1116594. As usual: “This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).” Finally, I’d like to thank all of my colleagues, friends, and relatives who encouraged me to write and to finish the book, Zeynep most of all. – Ryan O’Donnell Pittsburgh October 2013 Copyright © Ryan O’Donnell, 2014
List of Notation entry-wise multiplication of vectors the gradient:Vf(x)=(Dif(x),....Dnf(x)) > logical NOT 3 S3i is equivalent to ieS logical XOR (exclusive-or) (Eye度lfrP)p △ symmetric difference of sets;i.e.,SAT=i:i is in exactly one of S,T} logical OR A logical AND the convolution operator [z]F(z) coefficient on z in the power series F(z) 1A 0-1 indicator function for A 1B 0-1 indicator random variable for event B 24 the set of all subsets of A #a if a is a multi-index,denotes the number of nonzero com- ponents of a lal if a is a multi-index,denotes Liai ANDn the logical AND function on n bits:False unless all inputs are True A r:r.x=0 for all xeA) Aut(f) the group of automorphisms of Boolean function f xi进 Copyright@Ryan O'Donnell,2014
List of Notation ◦ entry-wise multiplication of vectors ∇ the gradient: ∇f (x) = (D1 f (x),...,Dn f (x)) ¬ logical NOT 3 S 3 i is equivalent to i ∈ S ⊕ logical XOR (exclusive-or) kˆ f kˆ p ( P γ∈❋cn 2 |fb(γ)| p ) 1/p 4 symmetric difference of sets; i.e., S4T = {i : i is in exactly one of S,T} ∨ logical OR ∧ logical AND ∗ the convolution operator [z k ]F(z) coefficient on z k in the power series F(z) 1A 0-1 indicator function for A 1B 0-1 indicator random variable for event B 2 A the set of all subsets of A #α if α is a multi-index, denotes the number of nonzero components of α |α| if α is a multi-index, denotes P i αi ANDn the logical AND function on n bits: False unless all inputs are True A ⊥ {γ : γ· x = 0 for all x ∈ A} Aut(f ) the group of automorphisms of Boolean function f xiii Copyright © Ryan O’Donnell, 2014
xiv List of Notation BitsToGaussians on input the bit matrix(-1,1)xM,has outputRd equaltotimes thecoisffdsmtted it's taken to be 1 C the complex numbers x(b) when beF2,denotes(-1)ER xs(x) when xe R",denotes Iliesxi,where Ss[n];when xeF2, denotes (-1)Eiesx codimH for a subspace Hs F",denotes n-dimH Cov[f,g] the covariance of f and g,Cov[f]=E[fg]-E[f]E[g] Di the ith discrete derivative:Df()= dx2(p,1) chi-squared distance of the distribution with density from the uniform distribution deg(f) the degree of f;the least k such that f is a real linear combination of k-juntas deg,(f) for Boolean-valued f,the degree of its F2-polynomial rep- resentation △(x,y) the Hamming distance,#fi:xi yi} △m(f) the expected number of queries made by the best decision tree computing f when the input bits are chosen from the distributionπ δm(f) the revealment off;ie.,min(maxi):computes f) △m(S) the expected number of queries made by randomized deci- sion tree when the input bits are chosen from the distri- butionπ 693) the probability randomized decision treequeries coor- dinate i when the input bits are chosen from the distribu- tionπ △yf forf:Fg一F2,the function F2一F2 defined by△yf(x)= f(x+y)-f(x) dist(g,h) the relative Hamming distance;i.e.,the fraction of inputs on which g and h disagree DNFsize(f) least possible size of a DNF formula computing f DNFwidth(f) least possible width of a DNF formula computing f DT(f) least possible depth of a decision tree computing f DTsize(f) least possible size of a decision tree computing f drv(o,w) total variation distance between the distributions with den- sities,Ψ Copyright@Ryan O'Donnell,2014
xiv List of Notation BitsToGaussiansd M on input the bit matrix x ∈ {−1,1} d×M, has output z ∈ ❘d equal to 1 p M times the column-wise sum of x; if d is omitted it’s taken to be 1 ❈ the complex numbers χ(b) when b ∈ ❋n 2 , denotes (−1)b ∈ ❘ χS(x) when x ∈ ❘n , denotes Q i∈S xi , where S ⊆ [n]; when x ∈ ❋n 2 , denotes (−1) P i∈S xi codimH for a subspace H ≤ ❋n , denotes n−dimH Cov[f , g] the covariance of f and g, Cov[f ] = E[f g]−E[f ]E[g] Di the ith discrete derivative: Di f (x) = f (x (i7→1))−f (x (i7→−1)) 2 dχ 2 (ϕ,1) chi-squared distance of the distribution with density ϕ from the uniform distribution deg(f ) the degree of f ; the least k such that f is a real linear combination of k-juntas deg❋2 (f ) for Boolean-valued f , the degree of its ❋2-polynomial representation ∆(x, y) the Hamming distance, #{i : xi 6= yi} ∆ (π) (f ) the expected number of queries made by the best decision tree computing f when the input bits are chosen from the distribution π δ (π) (f ) the revealment of f ; i.e., min{maxi δ (π) i (T ) : T computes f } ∆ (π) (T ) the expected number of queries made by randomized decision tree T when the input bits are chosen from the distribution π δ (π) i (T ) the probability randomized decision tree T queries coordinate i when the input bits are chosen from the distribution π ∆y f for f : ❋n 2 → ❋2, the function ❋n 2 → ❋2 defined by ∆y f (x) = f (x+ y)− f (x) dist(g,h) the relative Hamming distance; i.e., the fraction of inputs on which g and h disagree DNFsize(f ) least possible size of a DNF formula computing f DNFwidth(f ) least possible width of a DNF formula computing f DT(f ) least possible depth of a decision tree computing f DTsize(f ) least possible size of a decision tree computing f dTV(ϕ,ψ) total variation distance between the distributions with densities ϕ, ψ Copyright © Ryan O’Donnell, 2014
List of Notation XV Ei the ith expectation operator:Eif(x)=Ex:[f(x1,...,xi-1,i,xi+1,...,xn))] Er the expectation over coordinates I operator Ent[f] for a nonnegative function on a probability space,denotes E[fInf]-E[f]lnE[f] Ex,[-] an abbreviation for E[] f⊕g iff:{-1,1m-{-1,1}andg:{-1,1m-{-1,1,denotes the function h:(-1,1)m+n-(-1,1}defined by h(x,y)= f(x)g(y) f⑧g if f:(-1,1)m(-1,1)and g:(-1,1)7-(-1,1),denotes the function h:{-1,1ymn-(-1,1}defined by h(x(1),...,x(m))= f(g(x),.,gxrm》 fod if f:(-1,1yn-(-1,1),then fod :(-1,1ynd(-1,1)is de- fined inductively by f=f,fd+1)=ffed fin the n-fold convolution,f*f *...+f f the Boolean dual defined by ff(x)=-f(-x) f+2 if f F2-R,zEF2,denotes the function f+z(x)=f(x+z) f借 denotes (f+2)H F2 the finite field of size 2 度 the group (vector space)indexing the Fourier characters of functions f:Fg一R feven the even part of f,(f(x)+f(-x))/2 f,g〉 Ex[f(x)g(x)] fH if f:F2-R,HsF2,denotes the restriction of f to H f(i) shorthand for f((i})when ieN fsJ the function(depending only on the J coordinates)defined by f()=EIf(xJ,];in particular,it's scf(S)xs when f:(-1,1)"-R. fiz if f:O"-R,J[n],and denotes the restriction of f given by fixing the coordinates in J to z fJle iff:R,J[n],and z,denotes the restriction of f given by fixing the coordinates in to z k ∑1S1=kfS)xS fsk ∑IS1≤kfS)XS fodd the odd part of f,(f(x)-f(-x))/2 Ep for p prime and N+,denotes the finite field of p ele- ments Copyright Ryan O'Donnell,2014
List of Notation xv Ei the ith expectation operator: Ei f (x) = Exi [f (x1,..., xi−1, xi , xi+1,..., xn))] EI the expectation over coordinates I operator Ent[f ] for a nonnegative function on a probability space, denotes E[f ln f ]−E[f ] lnE[f ] Eπp [·] an abbreviation for Ex∼π ⊗n p [·] f ⊕ g if f : {−1,1} m → {−1,1} and g : {−1,1} n → {−1,1}, denotes the function h : {−1,1} m+n → {−1,1} defined by h(x, y) = f (x)g(y) f ⊗ g if f : {−1,1} m → {−1,1} and g : {−1,1} n → {−1,1}, denotes the function h : {−1,1} mn → {−1,1} defined by h(x (1) ,..., x (m) ) = f (g(x (1)),..., g(x (m) )) f ⊗d if f : {−1,1} n → {−1,1}, then f ⊗d : {−1,1} n d → {−1,1} is de- fined inductively by f ⊗1 = f , f ⊗(d+1) = f ⊗ f ⊗d f ∗n the n-fold convolution, f ∗ f ∗··· ∗ f f † the Boolean dual defined by f † (x) = −f (−x) f +z if f : ❋n 2 → ❘, z ∈ ❋n 2 , denotes the function f +z (x) = f (x+ z) f +z H denotes (f +z )H ❋2 the finite field of size 2 ❋cn 2 the group (vector space) indexing the Fourier characters of functions f : ❋n 2 → ❘ f even the even part of f , (f (x)+ f (−x))/2 〈f , g〉 Ex[f (x)g(x)] fH if f : ❋n 2 → ❘, H ≤ ❋n 2 , denotes the restriction of f to H fb(i) shorthand for fb({i}) when i ∈ ◆ f ⊆J the function (depending only on the J coordinates) defined by f ⊆J (x) = Ex 0 J [f (xJ, x 0 J )]; in particular, it’s P S⊆J fb(S)χS when f : {−1,1} n → ❘ f|z if f : Ωn → ❘, J ⊆ [n], and z ∈ ΩJ , denotes the restriction of f given by fixing the coordinates in J to z fJ|z if f : Ωn → ❘, J ⊆ [n], and z ∈ ΩJ , denotes the restriction of f given by fixing the coordinates in J to z f =k P |S|=k fb(S)χS f ≤k P |S|≤k fb(S)χS f odd the odd part of f , (f (x)− f (−x))/2 ❋p ` for p prime and ` ∈ ◆+, denotes the finite field of p ` elements Copyright © Ryan O’Donnell, 2014