xvi List of Notation f(s) the Fourier coefficient of f on character xs Fsf(z) for SJ[n],denotes fJ2(S) F the randomization/symmetrization of f,defined by f(r,x)= ∑srSf=S(x) Y(A) the Gaussian Minkowski content of oA g(v,p) the Erdos-Renyirandomgrapdistribution hj the jth (normalized)Hermite polynomial, ha for a e N"a multi-index,the n-variate (normalized)Her- mite polynomial ha(z)=I1ha,(zj) H the jth probabilists'Hermite polynomial,defined by exp(tz- 2)=20H(2w Infi[f] the influence of coordinate i on f Inff] the p-stable influence,Stabp[Dif] InfJ[f] the coalitional influence of J[n]on f:{-1,1)-(-1,1), namely Pr1 is not constant] Intlf] for bE(-1,1),equals Pr-1fJls]-Prif =b] 万 if J[n],denotes [n]\J L2(-1,1) denotes L2(-1,1)",) L2(G") if G is a finite abelian group,denotes the complex inner product space of functions G"-R with inner product (f,g)= Ex-Gr [f(x)g(x)] L2(0,π) the inner product space of(square-integrable)functions 2-R with inner product(f,g〉=Ex-π[f(x)g(x] A(a,) Pr[z1 s t,z2<t'],where z1,z2 are standard Gaussians with correlation E[z1z2]=p,and t=-1(a),t'=-1(B) Ap(a) denotes Ap(a,a) f the Laplacian operator applied to the Boolean function f, defined by Lf=Lif(or,the Ornstein-Uhlenbeck oper- ator if f is a function on Gaussian space) Li the ith coordinate Laplacian operator:Lif=f-Eif Inx logex logx log2x Majn the majority function on n bits MaxInflf] maxi(Infi[f ] [n] {1,2,3，.…,n Copyright@Ryan O'Donnell,2014
xvi List of Notation fb(S) the Fourier coefficient of f on character χS FS|J f (z) for S ⊆ J ⊆ [n], denotes fdJ|z(S) fe the randomization/symmetrization of f , defined by fe(r, x) = P S r S f =S (x) γ +(∂A) the Gaussian Minkowski content of ∂A G(v, p) the Erdos–Rényi random graph distribution, ˝ π ⊗( v 2 ) p hj the jth (normalized) Hermite polynomial, hj = p 1 j! Hj hα for α ∈ ◆n a multi-index, the n-variate (normalized) Hermite polynomial hα(z) = Qn j=1 hαj (z j) Hj the jth probabilists’ Hermite polynomial, defined by exp(tz− 1 2 t 2 ) = P∞ j=0 1 j! Hj(z)t j Infi[f ] the influence of coordinate i on f Inf(ρ) i [f ] the ρ-stable influence, Stabρ[Di f ] Inf gJ[f ] the coalitional influence of J ⊆ [n] on f : {−1,1} n → {−1,1}, namely Pr z∼{−1,1} J [fJ|z is not constant] Inf gb J [f ] for b ∈ {−1,1}, equals Pr z∼{−1,1} J [fJ|z 6≡ −b]−Pr[f = b] J if J ⊆ [n], denotes [n]\ J L 2 ({−1,1} n ) denotes L 2 ({−1,1} n ,π ⊗n 1/2) L 2 (G n ) if G is a finite abelian group, denotes the complex inner product space of functions G n → ❘ with inner product 〈f , g〉 = Ex∼Gn [f (x)g(x)] L 2 (Ω,π) the inner product space of (square-integrable) functions Ω → ❘ with inner product 〈f , g〉 = Ex∼π[f (x)g(x)] Λρ(α,β) Pr[z1 ≤ t, z2 ≤ t 0 ], where z1, z2 are standard Gaussians with correlation E[z1z2] = ρ, and t = Φ−1 (α), t 0 = Φ−1 (β) Λρ(α) denotes Λρ(α,α) Lf the Laplacian operator applied to the Boolean function f , defined by Lf = Pn i=1 Li f (or, the Ornstein–Uhlenbeck operator if f is a function on Gaussian space) Li the ith coordinate Laplacian operator: Li f = f −Ei f lnx loge x log x log2 x Majn the majority function on n bits MaxInf[f ] maxi{Infi[f ]} [n] {1,2,3,...,n} Copyright © Ryan O’Donnell, 2014
List of Notation xvii N 0,1,2,3,…} N+ {1,2,3， Nem 0,1,.,m-1 No(x) when xe(-1,1)",denotes the probability distribution gen- erating a string p-correlated to x Np(z) when z R",denotes the probability distribution of pz+ V1-p2g where g~N(0,1)n NSs[f] the noise sensitivity of f at i.e.,Stab1-2lf] N(0,1) the standard Gaussian distribution N(0,1)d the distribution of d independent standard Gaussians;i.e., N(O,Idxd) N(μ，) for ueRd and EERdxd positive semidefinite,the d-variate Gaussian distribution with mean u and covariance ma- trixE ORn the logical OR function on n bits:True unless all inputs are False φ the standard Gaussian pdf)= Φ the standard Gaussian cdf,()=(z)dz Φ the standard Gaussian complementary cdf,(t)=()dz PA the density function for the uniform probability distribu- tion on A;i.e.,1A/E[1A] a given functions o,...,m-1 and a multi-index a,denotes Π=1中a en if x is a probability distribution on denotes the associ- ated product probability distribution on π12 the uniform distribution on {-1,1) Ap the“p-biased'”distribution on bits:πp(-1)=p,πp(1)=1-p Prz[] an abbreviation for Prx-] R the real numbers R≥0 the nonnegative real numbers RDT(f) the zero-error randomized decision tree complexity of f RSA(6) the rotation sensitivity of A at 6;i.e.,Pr[1A(z)1A(2)]for a coso-correlated pair (z,z) sensf(x) the number of pivotal coordinates for f at x sgn(t) +1ift≥0，-1ift<0 Sn the symmetric group on [n] Copyright Ryan O'Donnell,2014
List of Notation xvii ◆ {0,1,2,3,...} ◆+ {1,2,3,...} ◆<m {0,1,...,m−1} Nρ(x) when x ∈ {−1,1} n , denotes the probability distribution generating a string ρ-correlated to x Nρ(z) when z ∈ ❘n , denotes the probability distribution of ρz + p 1−ρ 2g where g ∼ N(0,1)n NSδ[f ] the noise sensitivity of f at δ; i.e., 1 2 − 1 2 Stab1−2δ[f ] N(0,1) the standard Gaussian distribution N(0,1)d the distribution of d independent standard Gaussians; i.e., N(0, Id×d) N(µ,Σ) for µ ∈ ❘d and Σ ∈ ❘d×d positive semidefinite, the d-variate Gaussian distribution with mean µ and covariance matrix Σ ORn the logical OR function on n bits: True unless all inputs are False φ the standard Gaussian pdf, φ(z) = 1 p 2π e −z 2 /2 Φ the standard Gaussian cdf, Φ(t) = R t −∞ φ(z)dz Φ the standard Gaussian complementary cdf, Φ(t) = R ∞ t φ(z)dz ϕA the density function for the uniform probability distribution on A; i.e., 1A/E[1A] φα given functions φ0,...,φm−1 and a multi-index α, denotes Qn i=1 φαi π ⊗n if π is a probability distribution on Ω, denotes the associated product probability distribution on Ωn π1/2 the uniform distribution on {−1,1} πp the “p-biased” distribution on bits: πp(−1) = p, πp(1) = 1−p Prπp [·] an abbreviation for Prx∼π ⊗n p [·] ❘ the real numbers ❘≥0 the nonnegative real numbers RDT(f ) the zero-error randomized decision tree complexity of f RSA(δ) the rotation sensitivity of A at δ; i.e., Pr[1A(z) 6= 1A(z 0 )] for a cosδ-correlated pair (z, z 0 ) sensf (x) the number of pivotal coordinates for f at x sgn(t) +1 if t ≥ 0, −1 if t < 0 Sn the symmetric group on [n] Copyright © Ryan O’Donnell, 2014
xviii List of Notation sparsity(f) Prx[f(x)≠O] sparsity(f) Isupp(f) Stabp[f] the noise stability of f at p:E[f(a)f(y)]where x,y are a p-correlated pair supp(a) if a is a multi-index,denotes (i:ai#0) supp(f) if f is a function,denotes the set of inputs where f is nonzero Te the noise operator:Tof(x)=Ey-N()f(y)] the operator defined by Tof(x)=pf+(1-p)Eif Tr forrR",denotes the operator defined by T TT at the Gaussian isoperimetric function,=ΦoΦ-l Up the Gaussian noise operator:Upf(z)=E-N(2)[f(2)] Var[f] the variance of f,Var[f]=E[f2]-E[f]2 Vari the operator defined by Varif(x)=Varx:[f(x1,...,xi-1,i,xi+1,...,xn))] voly(A) Pr=-N(0.1)[ZEA],the Gaussian volume of A w[f] the Fourier weight of f at degree k W>[f打 the Fourier weight of f at degrees above k x(i-b) the string(x1,...,xi-1,6,xi+1,...,xn) ti (x1,,xi-1,-xi,xi+1,,3xn) x~p the random variable x is chosen from the probability distri- bution with density xS Ilies xi,with the conventionx=1 x~A the random variable x is chosen uniformly from the set A x~{-1,1 the random variable x is chosen uniformly from {-1,1)" (y,z) if J[n],ye(-1,1),(-1,1),denotes the natural com- posite string in (-1,1)n z the additive group of integers modulo m 然 the group indexing the Fourier characters of functions f: Zh一C Copyright Ryan O'Donnell,2014
xviii List of Notation sparsity(f ) Prx[f (x) 6= 0] sparsity(fb) |supp(fb)| Stabρ[f ] the noise stability of f at ρ: E[f (x)f (y)] where x, y are a ρ-correlated pair supp(α) if α is a multi-index, denotes {i : αi 6= 0} supp(f ) if f is a function, denotes the set of inputs where f is nonzero Tρ the noise operator: Tρ f (x) = Ey∼Nρ(x) [f (y)] T i ρ the operator defined by Ti ρ f (x) = ρ f +(1−ρ)Ei f Tr for r ∈ ❘n , denotes the operator defined by T1 r1 T 2 r2 ···T n rn U the Gaussian isoperimetric function, U = φ◦Φ−1 Uρ the Gaussian noise operator: Uρ f (z) = Ez 0∼Nρ(z) [f (z 0 )] Var[f ] the variance of f , Var[f ] = E[f 2 ]−E[f ] 2 Vari the operator defined by Vari f (x) = Varxi [f (x1,..., xi−1, xi , xi+1,..., xn))] volγ(A) Prz∼N(0,1)n [z ∈ A], the Gaussian volume of A Wk [f ] the Fourier weight of f at degree k W>k [f ] the Fourier weight of f at degrees above k x (i7→b) the string (x1,..., xi−1,b, xi+1,..., xn) x ⊕i (x1,..., xi−1,−xi , xi+1,..., xn) x ∼ ϕ the random variable x is chosen from the probability distribution with density ϕ x S Q i∈S xi , with the convention x ; = 1 x ∼ A the random variable x is chosen uniformly from the set A x ∼ {−1,1} n the random variable x is chosen uniformly from {−1,1} n (y, z) if J ⊆ [n], y ∈ {−1,1} J , z ∈ {−1,1} J , denotes the natural composite string in {−1,1} n ❩ the additive group of integers modulo m ❩dn m the group indexing the Fourier characters of functions f : ❩ n m → ❈ Copyright © Ryan O’Donnell, 2014
Chapter 1 Boolean functions and the Fourier expansion In this chapter we describe the basics of analysis of Boolean functions.We emphasize viewing the Fourier expansion of a Boolean function as its repre- sentation as a real multilinear polynomial.The viewpoint based on harmonic analysis over F2 is mostly deferred to Chapter 3.We illustrate the use of basic Fourier formulas through the analysis of the Blum-Luby-Rubinfeld linearity test. 1.1.On analysis of Boolean functions This is a book about Boolean functions, f:0,1)一{0,1. Here f maps each length-n binary vector,or string,into a single binary value, or bit.Boolean functions arise in many areas of computer science and mathe- matics.Here are some examples: In circuit design,a Boolean function may represent the desired behavior of a circuit with n inputs and one output. In graph theory,one can identify v-vertex graphs G with length-(2) strings indicating which edges are present.Then f may represent a property of such graphs;e.g.,f(G)=1 if and only if G is connected. In extremal combinatorics,a Boolean function f can be identified with a“set system”乎on[n]={l,2,.,nl,where sets X[n]are identified with their 0-1 indicators and Xe if and only if f(X)=1. 19 Copyright@Ryan O'Donnell,2014
Chapter 1 Boolean functions and the Fourier expansion In this chapter we describe the basics of analysis of Boolean functions. We emphasize viewing the Fourier expansion of a Boolean function as its representation as a real multilinear polynomial. The viewpoint based on harmonic analysis over ❋n 2 is mostly deferred to Chapter 3. We illustrate the use of basic Fourier formulas through the analysis of the Blum–Luby–Rubinfeld linearity test. 1.1. On analysis of Boolean functions This is a book about Boolean functions, f : {0,1} n → {0,1}. Here f maps each length-n binary vector, or string, into a single binary value, or bit. Boolean functions arise in many areas of computer science and mathematics. Here are some examples: • In circuit design, a Boolean function may represent the desired behavior of a circuit with n inputs and one output. • In graph theory, one can identify v-vertex graphs G with length-¡ v 2 ¢ strings indicating which edges are present. Then f may represent a property of such graphs; e.g., f (G) = 1 if and only if G is connected. • In extremal combinatorics, a Boolean function f can be identified with a “set system” F on [n] = {1,2,...,n}, where sets X ⊆ [n] are identified with their 0-1 indicators and X ∈ F if and only if f (X) = 1. 19 Copyright © Ryan O’Donnell, 2014
20 1.Boolean functions and the Fourier expansion In coding theory,a Boolean function might be the indicator function for the set of messages in a binary error-correcting code of length n. In learning theory,a Boolean function may represent a"concept"with n binary attributes. In social choice theory,a Boolean function can be identified with a "vot- ing rule"for an election with two candidates named 0 and 1. We will be quite flexible about how bits are represented.Sometimes we will use True and False;sometimes we will use-1 and 1,thought of as real numbers.Other times we will use 0 and 1,and these might be thought of as real numbers,as elements of the field F2 of size 2,or just as symbols.Most frequently we will use-1 and 1,so a Boolean function will look like f:{-1,1”-{-1,1. But we won't be dogmatic about the issue. We refer to the domain of a Boolean function,(-1,1)",as the Hamming cube (or hypercube,n-cube,Boolean cube,or discrete cube).The name "Ham- ming cube"emphasizes that we are often interested in the Hamming distance between strings x,ye[-1,1)",defined by △(x,y)=#{i:xi≠y}: Here we've used notation that will arise constantly:x denotes a bit string, and xi denotes its ith coordinate. Suppose you have a problem involving Boolean functions with the follow- ing two characteristics: the Hamming distance is relevant; you are counting strings,or the uniform probability distribution on {-1,1)"is involved. These are the hallmarks of a problem for which analysis of Boolean functions may help.Roughly speaking,this means deriving information about Boolean functions by analyzing their Fourier expansion. 1.2.The "Fourier expansion":functions as multilinear polynomials The Fourier expansion of a Boolean function f:(-1,1)m-(-1,1)is simply its representation as a real,multilinear polynomial.(Multilinear means that no variable xi appears squared,cubed,etc.)For example,suppose n=2 and Copyright@Ryan O'Donnell,2014
20 1. Boolean functions and the Fourier expansion • In coding theory, a Boolean function might be the indicator function for the set of messages in a binary error-correcting code of length n. • In learning theory, a Boolean function may represent a “concept” with n binary attributes. • In social choice theory, a Boolean function can be identified with a “voting rule” for an election with two candidates named 0 and 1. We will be quite flexible about how bits are represented. Sometimes we will use True and False; sometimes we will use −1 and 1, thought of as real numbers. Other times we will use 0 and 1, and these might be thought of as real numbers, as elements of the field ❋2 of size 2, or just as symbols. Most frequently we will use −1 and 1, so a Boolean function will look like f : {−1,1} n → {−1,1}. But we won’t be dogmatic about the issue. We refer to the domain of a Boolean function, {−1,1} n , as the Hamming cube (or hypercube, n-cube, Boolean cube, or discrete cube). The name “Hamming cube” emphasizes that we are often interested in the Hamming distance between strings x, y ∈ {−1,1} n , defined by ∆(x, y) = #{i : xi 6= yi}. Here we’ve used notation that will arise constantly: x denotes a bit string, and xi denotes its ith coordinate. Suppose you have a problem involving Boolean functions with the following two characteristics: • the Hamming distance is relevant; • you are counting strings, or the uniform probability distribution on {−1,1} n is involved. These are the hallmarks of a problem for which analysis of Boolean functions may help. Roughly speaking, this means deriving information about Boolean functions by analyzing their Fourier expansion. 1.2. The “Fourier expansion”: functions as multilinear polynomials The Fourier expansion of a Boolean function f : {−1,1} n → {−1,1} is simply its representation as a real, multilinear polynomial. (Multilinear means that no variable xi appears squared, cubed, etc.) For example, suppose n = 2 and Copyright © Ryan O’Donnell, 2014