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 ` ele￾ments Copyright © Ryan O’Donnell, 2014