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