1.6.Highlight:Almost linear functions and the BLR Test 31 1.6.Highlight:Almost linear functions and the BLR Test In linear algebra there are two equivalent definitions of what it means for a function to be linear: Definition 1.28.A function f:F2-F2 is linear if either of the following equivalent conditions hold: (1)f(x+y)=f(x)+f(y)for allx,yF3; (2)f(x)=a.x for some aeF2;i.e.,f(x)=Xies xi for some S[n]. Exercise 1.26 asks you to verify that the conditions are indeed equivalent. If we encode the output of f by t1 R in the usual way then the "linear" functions f:F2-(-1,1)are precisely the 2"parity functions(s)ssIn]. Let's think of what it might mean for a function f:F2-F2 to be approx- imately linear.Definition 1.28 suggests two possibilities: (1)f(x+y)=f(x)+f(y)for almost all pairs x,yeF2; (2)there is some Ss[n]such that f(x)=Xies xi for almost all xEF2 Are these equivalent?The proof of(2)=(1)in Definition 1.28 is "robust":it easily extends to show (2)(1)(see Exercise 1.26).But the natural proof of (1)=(2)in Definition 1.28 does not have this robustness property.The goal of this section is to show that(1)一（②）nevertheless holds. Motivation for this problem comes from an area of theoretical computer science called property testing,which we will discuss in more detail in Chap- ter 7.Imagine that you have "black-box"access to a function f:F2-F2, meaning that the function f is unknown to you but you can"query"its value on inputsxeF2 of your choosing.The function f is"supposed"to be a linear function,and you would like to try to verify this. The only way you can be certain f is indeed a linear function is to query its value on all 2"inputs;unfortunately,this is very expensive.The idea behind "property testing"is to try to verify that f has a certain property-in this case,linearity-by querying its value on just a few random inputs.In exchange for efficiency,we need to be willing to only approximately verify the property. Definition 1.29.If f and g are Boolean-valued functions we say they are e-close if dist(f,g)se;otherwise we say they are e-far.If is a (nonempty) property of n-bit Boolean functions we define dist(f,)=minges(dist(f,g)). We say that f is e-close to if dist(f,)se;i.e.,f is e-close to some g satisfying 9. Copyright Ryan O'Donnell,2014
1.6. Highlight: Almost linear functions and the BLR Test 31 1.6. Highlight: Almost linear functions and the BLR Test In linear algebra there are two equivalent definitions of what it means for a function to be linear: Definition 1.28. A function f : ❋n 2 → ❋2 is linear if either of the following equivalent conditions hold: (1) f (x+ y) = f (x)+ f (y) for all x, y ∈ ❋n 2 ; (2) f (x) = a· x for some a ∈ ❋n 2 ; i.e., f (x) = P i∈S xi for some S ⊆ [n]. Exercise 1.26 asks you to verify that the conditions are indeed equivalent. If we encode the output of f by ±1 ∈ ❘ in the usual way then the “linear” functions f : ❋n 2 → {−1,1} are precisely the 2n parity functions (χS)S⊆[n] . Let’s think of what it might mean for a function f : ❋n 2 → ❋2 to be approximately linear. Definition 1.28 suggests two possibilities: (10 ) f (x+ y) = f (x)+ f (y) for almost all pairs x, y ∈ ❋n 2 ; (20 ) there is some S ⊆ [n] such that f (x) = P i∈S xi for almost all x ∈ ❋n 2 . Are these equivalent? The proof of (2) =⇒ (1) in Definition 1.28 is “robust”: it easily extends to show (2 0 ) =⇒ (1 0 ) (see Exercise 1.26). But the natural proof of (1) =⇒ (2) in Definition 1.28 does not have this robustness property. The goal of this section is to show that (1 0 ) =⇒ (2 0 ) nevertheless holds. Motivation for this problem comes from an area of theoretical computer science called property testing, which we will discuss in more detail in Chapter 7. Imagine that you have “black-box” access to a function f : ❋n 2 → ❋2, meaning that the function f is unknown to you but you can “query” its value on inputs x ∈ ❋n 2 of your choosing. The function f is “supposed” to be a linear function, and you would like to try to verify this. The only way you can be certain f is indeed a linear function is to query its value on all 2n inputs; unfortunately, this is very expensive. The idea behind “property testing” is to try to verify that f has a certain property – in this case, linearity – by querying its value on just a few random inputs. In exchange for efficiency, we need to be willing to only approximately verify the property. Definition 1.29. If f and g are Boolean-valued functions we say they are ²-close if dist(f , g) ≤ ²; otherwise we say they are ²-far. If P is a (nonempty) property of n-bit Boolean functions we define dist(f ,P ) = ming∈P {dist(f , g)}. We say that f is ²-close to P if dist(f ,P ) ≤ ²; i.e., f is ²-close to some g satisfying P . Copyright © Ryan O’Donnell, 2014
32 1.Boolean functions and the Fourier expansion In particular,in property testing we take property(2)above to be the no- tion of"approximately linear":we say f is e-close to being linear if dist(f,g)se for some truly linear g(x)=Eies xi. In 1990 Blum,Luby,and Rubinfeld [BLR9O]showed that indeed (1)= (2')holds,giving the following"test"for the property of linearity that makes just 3 queries: BLR Test.Given query access to f:F2-F2: Choose x~F2 and y~F2 independently. Query f at x,y,and x+y. ·“Accept”iff(x)+f(y)=f(x+y). We now show that if the BLR Test accepts f with high probability then f is close to being linear.The proof works by directly relating the acceptance probability to the quantity sf(S)3;see equation(1.10)below. Theorem 1.30.Suppose the BLR Test accepts f:F2-F2 with probability 1-e.Then f is e-close to being linear. Proof.In order to use the Fourier transform we encode f's output by t1 R; thus the acceptance condition of the BLR Test becomes f(x)f(y)=f(x+y). Since 1 if f(x)f(y)=f(x+y), 壹++)={0ffef)≠f+ we conclude 1-e=PrBLR accepts/门=gr2+ff()f+y川 =壹+f)EIf()f(x+y川 =是+E[fx)(f*f(x切 (by definition) =+是∑fS)f*fS) (Plancherel) =+8∑fs3 (Theorem 1.27). Ssin] We rearrange this equality and then continue: 1-2e=fS)3 (1.10) SsIn] ((s)Fs SEIn] ((S) (Parseval). Copyright@Ryan O'Donnell,2014
32 1. Boolean functions and the Fourier expansion In particular, in property testing we take property (2 0 ) above to be the notion of “approximately linear”: we say f is ²-close to being linear if dist(f , g) ≤ ² for some truly linear g(x) = P i∈S xi . In 1990 Blum, Luby, and Rubinfeld [BLR90] showed that indeed (1 0 ) =⇒ (2 0 ) holds, giving the following “test” for the property of linearity that makes just 3 queries: BLR Test. Given query access to f : ❋n 2 → ❋2: • Choose x ∼ ❋n 2 and y ∼ ❋n 2 independently. • Query f at x, y, and x+ y. • “Accept” if f (x)+ f (y) = f (x+ y). We now show that if the BLR Test accepts f with high probability then f is close to being linear. The proof works by directly relating the acceptance probability to the quantity P S fb(S) 3 ; see equation (1.10) below. Theorem 1.30. Suppose the BLR Test accepts f : ❋n 2 → ❋2 with probability 1−². Then f is ²-close to being linear. Proof. In order to use the Fourier transform we encode f ’s output by ±1 ∈ ❘; thus the acceptance condition of the BLR Test becomes f (x)f (y) = f (x + y). Since 1 2 + 1 2 f (x)f (y)f (x+ y) = ( 1 if f (x)f (y) = f (x+ y), 0 if f (x)f (y) 6= f (x+ y), we conclude 1−² = Pr[BLR accepts f ] = E x,y [ 1 2 + 1 2 f (x)f (y)f (x+ y)] = 1 2 + 1 2 E x [f (x)·E y [f (y)f (x+ y)]] = 1 2 + 1 2 E x [f (x)·(f ∗ f )(x)] (by definition) = 1 2 + 1 2 X S⊆[n] fb(S)f∗ f (S) (Plancherel) = 1 2 + 1 2 X S⊆[n] fb(S) 3 (Theorem 1.27). We rearrange this equality and then continue: 1−2² = X S⊆[n] fb(S) 3 (1.10) ≤ max S⊆[n] {fb(S)}· X S⊆[n] fb(S) 2 = max S⊆[n] {fb(S)} (Parseval). Copyright © Ryan O’Donnell, 2014
1.7.Exercises and notes 33 But f(S)=(f,Is)=1-2dist(f,xs)(Proposition 1.9).Hence there exists some S*[n]such that 1-2es 1-2dist(f,xs.);i.e.,f is e-close to the linear function XS*. 口 In fact,for small e one can show that f is more like (e/3)-close to linear, and this is sharp.See Exercise 1.28. The BLR Test shows that given black-box access to f:F2-(-1,1),we can "test"whether f is close to some linear function xs using just 3 queries.The test does not reveal which linear function xs is close to (indeed,determining this takes at least n queries;see Exercise 1.27).Nevertheless,we can still determine the value of rs(x)with high probability for every xe2 of our choosing using just 2 queries.This property is called local correctability of linear functions. Proposition 1.31.Suppose f:F2-{-1,1)is e-close to the linear function xs. Then for every xF2,the following algorithm outputs xs(x)with probability at least 1-2e: ·Choose y~F ·Query f at y and x+y. ·Output f(y)f(x+y) We emphasize the order of quantifiers here:if we just output f(x)then this will equal xs(x)for most x;however,the above "local correcting"algorithm determines xs(x)(with high probability)for every x. Proof.Since y and x+y are both uniformly distributed on F2(though not independently)we have Pr[f(y)≠Xs(y]se and Pr[f(x+y)≠xs(x+yl≤e by assumption.By the union bound,the probability of either event occurring is at most 2e:when neither occurs, f(y)f(x+y)=xs(y)xs(x+y)=xs(x) as desired. 口 1.7.Exercises and notes 1.1 Compute the Fourier expansions of the following functions: (a)min2:(-1,1)2-(-1,1),the minimum function on 2 bits (also known as the logical OR function); (6)min3:{-1,13-(-1,1)and max3:{-1,13→{-1,1； (c)the indicator function 1a):F2-(0,1),where aF2; (d)the density function )F2-R=0,where aF2; (e)the density function p.:F2-R=0,where a and ei= (0,...,0,1,0,...,0)with the 1 in the ith coordinate; Copyright@Ryan O'Donnell,2014
1.7. Exercises and notes 33 But fb(S) = 〈f ,χS〉 = 1−2dist(f ,χS) (Proposition 1.9). Hence there exists some S ∗ ⊆ [n] such that 1−2² ≤ 1−2dist(f ,χS∗ ); i.e., f is ²-close to the linear function χS∗ . In fact, for small ² one can show that f is more like (²/3)-close to linear, and this is sharp. See Exercise 1.28. The BLR Test shows that given black-box access to f : ❋n 2 → {−1,1}, we can “test” whether f is close to some linear function χS using just 3 queries. The test does not reveal which linear function χS is close to (indeed, determining this takes at least n queries; see Exercise 1.27). Nevertheless, we can still determine the value of χS(x) with high probability for every x ∈ ❋n 2 of our choosing using just 2 queries. This property is called local correctability of linear functions. Proposition 1.31. Suppose f : ❋n 2 → {−1,1} is ²-close to the linear function χS. Then for every x ∈ ❋n 2 , the following algorithm outputs χS(x) with probability at least 1−2²: • Choose y ∼ ❋n 2 . • Query f at y and x+ y. • Output f (y)f (x+ y). We emphasize the order of quantifiers here: if we just output f (x) then this will equal χS(x) for most x; however, the above “local correcting” algorithm determines χS(x) (with high probability) for every x. Proof. Since y and x + y are both uniformly distributed on ❋n 2 (though not independently) we have Pr[f (y) 6= χS(y)] ≤ ² and Pr[f (x + y) 6= χS(x + y)] ≤ ² by assumption. By the union bound, the probability of either event occurring is at most 2²; when neither occurs, f (y)f (x+ y) = χS(y)χS(x+ y) = χS(x) as desired. 1.7. Exercises and notes 1.1 Compute the Fourier expansions of the following functions: (a) min2 : {−1,1} 2 → {−1,1}, the minimum function on 2 bits (also known as the logical OR function); (b) min3 : {−1,1} 3 → {−1,1} and max3 : {−1,1} 3 → {−1,1}; (c) the indicator function 1{a} : ❋n 2 → {0,1}, where a ∈ ❋n 2 ; (d) the density function ϕ{a} : ❋n 2 → ❘≥0 , where a ∈ ❋n 2 ; (e) the density function ϕ{a,a+ei} : ❋n 2 → ❘≥0 , where a ∈ ❋n 2 and ei = (0,...,0,1,0,...,0) with the 1 in the ith coordinate; Copyright © Ryan O’Donnell, 2014.
34 1.Boolean functions and the Fourier expansion (f)the density function corresponding to the product probability distri- bution on (-1,1)"in which each coordinate has mean pe[-1,1]; (g)the inner product mod 2 function,IPan:(-1,1}defined by IP2n(x1,...,xn,y1,...,yn)=(-1)*y; (h)the equality function Equn:(-1,1)"-(0,1),defined by Equ(x)=1 if and only if x1=x2=.=xn; (i)the not-all-equal function NAEn:(-1,1)"-(0,1),defined by NAEn(x)= 1 if and only if the bits x1,...,xn are not all equal; (the selection function,Sel:(-1,1)3-(-1,1),which outputs x2 ifx1= -1 and outputs x3 if x1=1; (k)mods:F3-(0,1),which is 1 if and only if the number of 1's in the input is divisible by 3; (Z)OXR:3-(0,1}defined by OXR(x1,x2,x3)=x1V(x2 x3).Here v de- notes logical OR,denotes logical XOR; (m)the sortedness function Sort4:(-1,1)4-(-1,1),defined by Sorta(x)= -1 if and only if x1≤x2≤xg≤x4orx1≥x2≥x3≥x4 (n)the hemi-icosahedron function HI:{-1,1)6-{-1,1}(also known as the Kushilevitz function),defined to be the number of facets labeled (+1,+1,+1)in Figure 1.2,minus the number of facets labeled(-1,-1,-1), modulo 3. 2x4 2x5 30 X1 3x2 x3 X5 X4 Figure 1.2.The hemi-icosahedron (Hint:First compute the real multilinear interpolation of the ana- logue HI:{0,1}6一{0,1.) (o)the majority functions Majs:(-1,1)5-(-1,1)and Majz:(-1,1)7 {-1,1; (p)the complete quadratic function CQn:F2-(-1,1}defined by CQn(x)= X(isi<jsnxixj).(Hint:Determine CQn (x)as a function of the num- ber of I's in the input modulo 4.You'll want to distinguish whether n is even or odd.) Copyright Ryan O'Donnell,2014
34 1. Boolean functions and the Fourier expansion (f) the density function corresponding to the product probability distribution on {−1,1} n in which each coordinate has mean ρ ∈ [−1,1]; (g) the inner product mod 2 function, IP2n : ❋2n 2 → {−1,1} defined by IP2n(x1,..., xn, y1,..., yn) = (−1)x·y ; (h) the equality function Equn : {−1,1} n → {0,1}, defined by Equn (x) = 1 if and only if x1 = x2 = ··· = xn; (i) the not-all-equal function NAEn : {−1,1} n → {0,1}, defined by NAEn(x) = 1 if and only if the bits x1,..., xn are not all equal; (j) the selection function, Sel : {−1,1} 3 → {−1,1}, which outputs x2 if x1 = −1 and outputs x3 if x1 = 1; (k) mod3 : ❋3 2 → {0,1}, which is 1 if and only if the number of 1’s in the input is divisible by 3; (l) OXR : ❋3 2 → {0,1} defined by OXR(x1, x2, x3) = x1 ∨(x2 ⊕ x3). Here ∨ denotes logical OR, ⊕ denotes logical XOR; (m) the sortedness function Sort4 : {−1,1} 4 → {−1,1}, defined by Sort4(x) = −1 if and only if x1 ≤ x2 ≤ x3 ≤ x4 or x1 ≥ x2 ≥ x3 ≥ x4; (n) the hemi-icosahedron function HI : {−1,1} 6 → {−1,1} (also known as the Kushilevitz function), defined to be the number of facets labeled (+1,+1,+1) in Figure 1.2, minus the number of facets labeled (−1,−1,−1), modulo 3. Figure 1.2. The hemi-icosahedron (Hint: First compute the real multilinear interpolation of the analogue HI : {0,1} 6 → {0,1}.) (o) the majority functions Maj5 : {−1,1} 5 → {−1,1} and Maj7 : {−1,1} 7 → {−1,1}; (p) the complete quadratic function CQn : ❋n 2 → {−1,1} defined by CQn(x) = χ( P 1≤i<j≤n xixj). (Hint: Determine CQn(x) as a function of the number of 1’s in the input modulo 4. You’ll want to distinguish whether n is even or odd.) Copyright © Ryan O’Donnell, 2014
1.7.Exercises and notes 35 1.2 How many Boolean functions f:{-1,1)"{-1,1)have exactly 1 nonzero Fourier coefficient? 1.3 Let f:F2(0,1)and suppose #x:f(x)=1)is odd.Prove that all of f's Fourier coefficients are nonzero. 1.4 Let f:(-1,1)"-R have Fourier expansion f(x)=Essinf(S)xS.Let F: R-Rbe the extension of f which is also defined by F(x)=sf(S)xS. Show that ifμ=(，…，4n)e[-l,1]"then F(）=E[f(yl, where y is the random string in (-1,1)"defined by having E[yil =ui independently for all ie[n]. 1.5 Prove that any f:(-1,1)"-(-1,1}has at most one Fourier coefficient with magnitude exceeding 1/2.Is this also true for any f:(-1,1)-R. with llfll2 1? 1.6 Use Parseval's Theorem to prove uniqueness of the Fourier expansion. 1.7 Let f:(-1,1)"-(-1,1)be a random function (i.e.,each f(x)is +1 with probability 1/2,independently for all xe[-1,1)").Show that for each S[n],the random variable f(S)has mean 0 and variance 2-".(Hint: Parseval.) 1.8 The (Boolean)dual of f:(-1,1)"-R is the function ff defined by ff(x)= -f(-x).The function f is said to be odd if it equals its dual;equivalently, if f(-x)=-f(x)for all x.The function f is said to be even if f(-x)=f(x) for all x.Given any function f:(-1,1)"-R,its odd part is the function fodd:(-1,1yn-R defined by fodd(x)=(f(x)-f(-x))/2,and its even part is the function feven (-1,1)n-R defined by feven(x)=(f(x)+f(-x))/2. (a)Express ff(S)in terms of f(S). (b)Verify thatf=fodd+feven and that f is odd (respectively,even)if and only if f=fodd (respectively,f=feven). (c)Show that fodd=∑fS)xs, feven=厂 f(S)xs ScIn] ISI odd SI even 1.9 In this problem we consider representing False,True as 0,1E R. (a)Using the interpolation method from Section 1.2,show that every f: (False,True)"-(False,True)can be represented as a real multilinear polynomial q(x)=∑csΠx, (1.11) SsIn]ieS “over{0,l”,meaning mapping{0,1一{0，l. Copyright@Ryan O'Donnell,2014
1.7. Exercises and notes 35 1.2 How many Boolean functions f : {−1,1} n → {−1,1} have exactly 1 nonzero Fourier coefficient? 1.3 Let f : ❋n 2 → {0,1} and suppose #{x : f (x) = 1} is odd. Prove that all of f ’s Fourier coefficients are nonzero. 1.4 Let f : {−1,1} n → ❘ have Fourier expansion f (x) = P S⊆[n] fb(S) x S . Let F : ❘n → ❘ be the extension of f which is also defined by F(x) = P S⊆[n] fb(S) x S . Show that if µ = (µ1,...,µn) ∈ [−1,1]n then F(µ) = E y [f (y)], where y is the random string in {−1,1} n defined by having E[yi ] = µi independently for all i ∈ [n]. 1.5 Prove that any f : {−1,1} n → {−1,1} has at most one Fourier coefficient with magnitude exceeding 1/2. Is this also true for any f : {−1,1} n → ❘ with kf k2 = 1? 1.6 Use Parseval’s Theorem to prove uniqueness of the Fourier expansion. 1.7 Let f : {−1,1} n → {−1,1} be a random function (i.e., each f (x) is ±1 with probability 1/2, independently for all x ∈ {−1,1} n ). Show that for each S ⊆ [n], the random variable bf (S) has mean 0 and variance 2−n . (Hint: Parseval.) 1.8 The (Boolean) dual of f : {−1,1} n → ❘ is the function f † defined by f † (x) = −f (−x). The function f is said to be odd if it equals its dual; equivalently, if f (−x) = −f (x) for all x. The function f is said to be even if f (−x) = f (x) for all x. Given any function f : {−1,1} n → ❘, its odd part is the function f odd : {−1,1} n → ❘ defined by f odd(x) = (f (x)− f (−x))/2, and its even part is the function f even : {−1,1} n → ❘ defined by f even(x) = (f (x)+ f (−x))/2. (a) Express cf † (S) in terms of fb(S). (b) Verify that f = f odd+ f even and that f is odd (respectively, even) if and only if f = f odd (respectively, f = f even). (c) Show that f odd = X S⊆[n] |S| odd fb(S)χS, f even = X S⊆[n] |S| even fb(S)χS. 1.9 In this problem we consider representing False,True as 0,1 ∈ ❘. (a) Using the interpolation method from Section 1.2, show that every f : {False,True} n → {False,True} can be represented as a real multilinear polynomial q(x) = X S⊆[n] cS Y i∈S xi , (1.11) “over {0,1}”, meaning mapping {0,1} n → {0,1}. Copyright © Ryan O’Donnell, 2014