Derandomization from Algebraic Hardness: Treading the Borders
Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon · 2019
A hitting-set generator (HSG) is a polynomial map Gen:Fk→ Fnsuch that for all n-variate polynomials Q of small enough circuit size and degree, if Q is non-zero, then Q o Gen is non-zero. In this paper, we give a new construction of such a HSG assuming that we have an explicit polynomial of sufficient hardness in the sense of approximative or border complexity. Formally, we prove the following result over any characteristic zero field F: Suppose P(z1,..., zk) is an explicit k-variate degree d polynomial that is not in the border of circuits of size s. Then, there is an explicit hitting-set generator Gen(P): F2k→ Fnsuch that every non-zero n-variate degree D polynomial Q(x) in the border of size s' circuits satisfies Q ≠ 0 ⇒ Q o Gen(P) ≠ 0 provided n10kd Ds'0 be a constant and k be a large enough constant. Suppose, for every s ≥ k, there is an explicit hitting set of size sk-δfor all degree s polynomials in the border of k-variate size s algebraic circuits. Then, there is an explicit hitting set of size poly(s) for the border s-variate algebraic circuits of size s and degree s. Unlike the prior constructions of such maps (e.g.[NW94], [KI04], [AGS19], [KST19]), our construction is purely algebraic and does not rely on the notion of combinatorial designs.