TR22-132 Authors: Harm Derksen, Emanuele Viola

Publication: 18th September 2022 23:32

Downloads: 153

Keywords:

We revisit the problem of constructing explicit pseudorandom generators

that fool with error $\epsilon$ degree-$d$ polynomials in $n$ variables

over the field $F_q$, in the case of large $q$. Previous constructions

either have seed length at least $2^{d}\log q$, and thus are only non-trivial

when the degree is less than $\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 at least $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 less than $\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>d^{4}$.