In this paper, two structural results concerning low degree polynomials over the field F2 are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of Fn2 with dimension (n1(d−1)) on which f is constant. This result is shown to be tight. Stated differently, a degree d polynomial cannot compute an affine disperser for dimension smaller than (n1(d−1)) . Using a recursive argument, we obtain our second structural result, showing that any degree d polynomial f induces a partition of Fn2 to affine subspaces of dimension (n1(d−1)!) , such that f is constant on each part. We extend both structural results to more than one polynomial, and consider the algorithmic aspect of these results.

Our structural results have various applications:

* Dvir [CC 2012] introduced the notion of extractors for varieties, and gave explicit constructions of such extractors over large fields. We show that over F2, any affine extractor is also an extractor for varieties, with related parameters. Our reduction also holds for dispersers, and we conclude that Shaltiel's affine disperser [FOCS 2011] is a disperser for varieties over F2.

* Ben-Sasson and Kopparty [SIAM J. Computing 2012] proved that any degree 3 affine disperser is also an affine extractor with related parameters. Using our structural results, and based on the work of Kaufman and Lovett [FOCS 2008] and Haramaty and Shpilka [STOC 2010], we generalize this result to any constant degree.

* Implicit in Razborov's work [CAAML 1988], the existence of a depth 3 AC0[] circuit that computes an optimal affine extractor was shown. We complement this result by showing that depth 2 AC0[] circuits cannot compute affine dispersers for sub-polynomial dimension. This can be interpreted as a generalization of our structural results to sparse polynomials (regardless of their degree). We also give an alternative proof for the depth 3 case.

We deduce several other corollaries from the structural results, one of which states that any excellent affine extractor has small correlation with low degree polynomials. Another is a lower bound on the granularity of the Fourier spectrum of low degree polynomials.