A hitting-set generator (HSG) is a polynomial map G : F k F n such that for all n -variate polynomials C of small enough circuit size and degree, if C is nonzero, then C G is nonzero. In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following result over any field F of characteristic zero:

Suppose P ( z 1 z k ) is an explicit k -variate degree d polynomial that is not computable by circuits of size s . Then, there is an explicit HSG G P : F 2 k F n such that every nonzero n -variate degree D polynomial C ( x ) computable by circuits of size s circuits satisfies C = 0 C G P = 0 , if O ( n 10 k d 3 D s ) s .

This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. Unlike the prior constructions of such maps, our construction is purely algebraic and does not rely on the notion of combinatorial designs.As a direct consequence, we show that even saving a single point from the ``trivial'' explicit, exponential sized hitting sets for constant-variate polynomials of low individual-degree which are computable by small circuits, implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following:

Let k be a large enough constant. Suppose for every s large enough, there is an explicit hitting set of size at most (( s + 1 ) k − 1 ) for the class of k -variate polynomials of individual degree s that are computable by size s circuits. Then there is an explicit hitting set of size s O ( k 2 ) for the class of s -variate polynomials, of degree s , that are computable by size s circuits.