Derandomization from Algebraic Hardness
share
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^2k→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^10kd^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.
READ FULL TEXT