# Two Structural Results for Low Degree Polynomials and Applications

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 \(\mathbb{F}_2\), 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 \(\mathbb{F}_2\).

* 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 \(\mathrm{AC}^0[\oplus]\) circuit that computes an optimal affine extractor was shown. We complement this result by showing that depth 2 \(\mathrm{AC}^0[\oplus]\) 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.

Joint work with Gil Cohen.