Derandomization from Algebraic Hardness: Treading the Borders

Abstract

A hitting-set generator (HSG) is a polynomial map Gen:F <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> → F <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> such 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(z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ,..., z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> ) 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): F <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2k</sup> → F <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> such 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 n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">10k</sup> d Ds'<; 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. As a direct consequence, we show that even a slightly non-trivial explicit construction of hitting sets for polynomials in the border of constant-variate circuits implies a deterministic polynomial time algorithm for PIT. Let δ > 0 be a constant and k be a large enough constant. Suppose, for every s ≥ k, there is an explicit hitting set of size s <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k-δ</sup> 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.