Fooling polynomials using invariant theory*

We revisit the problem of constructing explicit pseudorandom generators that fool with error ϵ degree-d polynomials in n variables over the field Fq, in the case of large q. Previous constructions either have seed length $\geq 2^{d}\log q$, and thus are only non-trivial when $d\lt \log n$, or else rely on a seminal reduction by Bogdanov (STOC 2005). This reduction yields seed length not less than $d^{4}\log n+\log q$ and requires fields of size $q\geq d^{6}/\epsilon^{2}$; and explicit generators meeting such bounds are known.Departing from Bogdanov’s reduction, we develop an algebraic analogue of the Bogdanov-Viola paradigm (FOCS 2007, SICOMP 2010) of summing generators for degree-one polynomials. Whereas previous analyses of the paradigm are restricted to degree $d\lt \log n$, we give a new analysis which handles large degrees. A main new idea is to show that the construction preserves indecomposability of polynomials. Apparently for the first time in the area, the proof uses invariant theory.Our approach in particular yields several new pseudorandom generators. In particular, for large enough fields we obtain seed length $O(d\log n+\log q)$ which is optimal up to constant factors. We also construct generators for fields of size as small as $O(d^{4})$. Further reducing the field size requires a significant change in techniques: Most or all generators for large-degree polynomials rely on Weil bounds; but such bounds are only applicable when $q\gt d^{4}$