.. (לתיקייה המכילה) | ||
In Q2, what is e? | |
e is epsilon. |
In Q1, in what sense T is linear? | |
You should think of f as a function between two subsets of R. Linear function in this sense is a function of the form f(x)=ax+b, where the operations are over R. |
In Q6: can f' be a constant? | |
No. Assume that f' is not constant. |
In Q1b: What is the inner product, for functions from {-1,1}^n? | |
<f,g> is the expectation of f(x)g(x) where x is chosen uniformly from {-1,1}^n |
In Q4: What is the multivariate polynomial representing f? | |
It can be shown that for any function f from {0,1}^n to {-1,1} there is a unique multilinear polynomial p over R such that f(x)=p(x) for every x in {0,1}^n. p is the multivariate polynomial representing f. (you can prove it by solving the linear system where the variables are the coefficients and the equations are f(x)=p(x) for every x) |
In Q6: Can I get a hint? | |
*********************************************************************** SPOILER ALERT *********************************************************************** In section a: Notice that f'^2 = 1. Write this equation in Fourier basis. In section 2: Notice that deg(f + x_1 + ... +x_n) = deg(f) (as polynomial over GF(2)). What does this equation say about the Fourier coefficients of f'? |