In computer science,we run into Boolean functions a lot.There are two ways of writing expressing a Boolean value-{0,l}or{+1,-1}.Note that the group Z2兰({0,1}，⊕)兰 ({+1,-1),.),where and.are the XOR and multiplication,respectively.These two ways of representing a Boolean value can be exchanged easily as follows.Suppose that we use f for {0,1)-valued function and g for the same function but with range {+1,-1),then f=(1-g)/2,andg=1-2f For Boolean functions with range (+1,-1],we have the following fact. Parseval Identity.For any function f:{0,1}n→{+1，-1}，we have∑af(a)2=1 So one can view f(a)2 as a distribution over all a E (0,1)n. 2.F2-degree,discrete derivatives For Boolean functions f:(0,1)n[0,1],we can either view them as a polynomial over R or a polynomial over F2. Exercise.For the Parity function of 2 bits,write down it as a polynomial f E R[x,x]and f∈F2[x1,x2l Whenever we have a polynomial,we can talk about its degree.Note from the above example that the degree of f as a polynomial over R or that over F2 are different.We denote by deg(f)and deg2(f)the degrees f as a polynomial over R and that over F2, respectively. One interesting operator on functions is the derivative.For any f:{0,1)n[0,1}and any direction vector t E(0,1)",the discrete derivative of f along the direction t is another function △f:{0,1}n→{0,1}defined by△：f(x)=f(x)+f(x+t) Note that when we talk about polynomials over F2,all additions in the above equation are also over F2. Just as derivatives for polynomials over R,the discrete derivative also decrease the degree of a polynomial.That is,In computer science, we run into Boolean functions a lot. There are two ways of writing expressing a Boolean value---{0,1} or {+1, −1}. Note that the group ℤ2 ≅ ({0,1}, ⊕) ≅ ({+1, −1}, ⋅ ), where ⊕ and ⋅ are the XOR and multiplication, respectively. These two ways of representing a Boolean value can be exchanged easily as follows. Suppose that we use 𝑓 for {0,1}-valued function and 𝑔 for the same function but with range {+1, −1}, then 𝑓 = (1 − 𝑔)/2, and 𝑔 = 1 − 2𝑓. For Boolean functions with range {+1, −1}, we have the following fact. Parseval Identity. For any function 𝑓:{0,1} 𝑛 → {+1, −1}, we have ∑ 𝑓̂(𝛼) 2 𝛼 = 1. So one can view 𝑓̂(𝛼) 2 as a distribution over all 𝛼 ∈ {0,1} 𝑛 . 2. 𝔽𝟐 -degree, discrete derivatives For Boolean functions 𝑓:{0,1} 𝑛 → {0,1}, we can either view them as a polynomial over ℝ or a polynomial over 𝔽2 . Exercise. For the Parity function of 2 bits, write down it as a polynomial 𝑓 ∈ ℝ[𝑥1 ,𝑥2 ] and 𝑓 ∈ 𝔽2 [𝑥1 ,𝑥2 ]. Whenever we have a polynomial, we can talk about its degree. Note from the above example that the degree of 𝑓 as a polynomial over ℝ or that over 𝔽2 are different. We denote by deg(𝑓) and deg2 (𝑓) the degrees 𝑓 as a polynomial over ℝ and that over 𝔽2 , respectively. One interesting operator on functions is the derivative. For any 𝑓:{0,1} 𝑛 → {0,1} and any direction vector 𝑡 ∈ {0,1} 𝑛 , the discrete derivative of 𝑓 along the direction 𝑡 is another function 𝛥𝑡𝑓: {0,1} 𝑛 → {0,1} defined by 𝛥𝑡𝑓(𝑥) = 𝑓(𝑥) + 𝑓(𝑥 + 𝑡) Note that when we talk about polynomials over 𝔽2 , all additions in the above equation are also over 𝔽2 . Just as derivatives for polynomials over ℝ, the discrete derivative also decrease the degree of a polynomial. That is