Polynomials and subspaces

My latest post on Szemeredi's theorem was long and rambling, mostly because I had no idea what I was talking about. There are, however, a couple of neat questions, and I am afraid they got lost in the rambling, so let me state them again.

1. It is either known or probably derivable from known proof techniques that
   

   If f:{0,1}^n -> {0,1} has agreement 1/2+eps with a degree-k polynomial, then there is an affine subspace V of {0,1}ⁿ, of dimension n/c, and a linear function L, such that f and L have agreement 1/2 + eps' when restricted to V. Here c=c(k) is a constant that depends only on k and eps'=eps'(eps,k) is a constant that depends only on eps and on k.

   
   This is somewhat surprising, even if you look at the special case of a function f that is a polynomial (as opposed to being correlated with a polynomial).
   
   Is there a simple proof of this result? Is the result true if you replace "subspace" by "restriction"? (Meaning, you are only allowed to fix all but a constant fraction of the variables.) Shouldn't this be useful in complexity theory somewhere?
   
   [Update 7/14/06: the degree-2 case has indeed a very simple proof. A more general result is proved here, in section 7. For higher degree, the result is actually false, in the sense that it is impossible to find a subspace of dimension constant*n. Avi Wigderson and I have found a counterexample already for degree 3, and Ben Green has sharpened our lower bound. The best one can do for degree-k polynomials is to find a subspace of dimension about n^(1/(k-1)).]
   
   



2. If f has agreement 1/2+eps with a linear function L in a subspace V of dimension n-t, then there is a linear function L' such that f and L' agree on a fraction at least 1/2+eps/2^t of all of {0,1}ⁿ
   
   This is fairly easy to see.
   
   
3. This is a fascinating challenge: find an simple proof (or any proof that fits in fewer than, say, 20 pages) that if f:{0,1}ⁿ->{-1,1} has dimension-k Gowers uniformity at least eps, then there is a linear subspace V of dimension n/c and a linear function L, such that f and L have agreement at least 1/2+eps' on V. (Where c=c(k) and eps'=eps'(eps,k).)
   
   Chances are that such a proof could be turned into a simpler proof of Gowers's quantitative version of Szemeredi's theorem. (A proof of the above result for boolean functions can probably be "translated back" from Gowers's paper, and it would probably be at least 50-60 pages. As I understand it, such a proof would first argue that f is correlated with a polynomial in a large subspace, and then proceed with (1) above. I wonder: can one prove such a statement without mentioning polynomials at all?)
   
   
4. Unfortunately the conclusion cannot be strenghtened to "... there is a linear subspace V of dimension n-o(n)...". Consider
   

   f(x₁,...,x₁):= x₁*x₂+...+ x_n-1*x_n mod 2

   
   Its dimension-3 Gowers uniformity is 1, but, if you could find a subspace V of dimension n-o(n) on which f agrees with a linear function on a 1/2+eps' fraction of inputs, then you could also find a linear function that agrees with f on a 1/2+eps/2^o(n) fraction of inputs. But we know that no linear function agrees with f on more than a 1/2+1/2^n/2 fraction of inputs.