ICTS

We will present a proof of the following theorem using properties of the characters of the group Z_2^n. 
Theorem: Fix eps in [0,1].  Suppose f: Z_2^n --> Z_2 is such that for x, y chosen uniformly at random from Z_2^n, we have 
Pr[ f(x+y) = f(x) + f(y) ]  >= 1 - eps.
Then, there is a linear function g: Z_2^n --> Z_2 such that for x chosen uniformly at random from Z_2^n, we have
Pr[ f(x) = g(x) ] >= 1 - eps. (End of theorem)
(This is a somewhat precise version of a theorem originally proved using a combinatorial argument by Blum, Luby and Rubinfeld.) We will assume no background in computer science or in representation theory; we will begin by reviewing the characters of Z_2^n and their properties. If there is time left, we will present another algebraic result in the same spirit.