Two Structural Results for Low Degree Polynomials and Applications

We give two structural results concerning low degree polynomials over the field $$\mathbb{F}_2$$. The first states that for any degree d polynomial f in n variables, there exists a subspace of $$\mathbb{F}_2^n$$ with dimension $$\Omega(n^{1/(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 $$\Omega(n^{1/(d-1)})$$. Using a recursive argument, we obtain our second structural result, showing that any degree d polynomial f induces a partition of $$\mathbb{F}_2^n$$ to affine subspaces of dimension $$\Omega(n^{1/(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 $$\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.

Affiliation

Weizmann Institute