ECCC-Report TR22-132https://eccc.weizmann.ac.il/report/2022/132Comments and Revisions published for TR22-132en-usSun, 18 Sep 2022 23:32:26 +0300
Paper TR22-132
| Fooling polynomials using invariant theory |
Harm Derksen,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2022/132We 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}$.Sun, 18 Sep 2022 23:32:26 +0300https://eccc.weizmann.ac.il/report/2022/132