Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-132 | 18th September 2022 23:31

Fooling polynomials using invariant theory


Authors: Harm Derksen, Emanuele Viola
Publication: 18th September 2022 23:32
Downloads: 609


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}$.

ISSN 1433-8092 | Imprint