Derandomization from Algebraic Hardness: Treading the Borders.

A hitting-set generator (HSG) is a polynomial map $Gen:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $Q$ of small enough circuit size and degree, if $Q$ is non-zero, then $Q\circ 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 $\mathbb{F}$: Suppose $P(z_1,\ldots, z_k)$ 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:\mathbb{F}^{2k} \rightarrow \mathbb{F}^n$ such that every non-zero $n$-variate degree $D$ polynomial $Q(x_1, x_2, \ldots, x_n)$ in the border of size $s'$ circuits satisfies $Q \neq 0 \Rightarrow Q \circ \mathsf{Gen}_P \neq 0$, provided $n^{10k}d^2 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. As a direct consequence, we prove the following bootstrapping result for PIT: Let $\delta > 0$ be any constant and $k$ be a large enough constant. Suppose, for every $s \geq k$, there is an explicit hitting set of size $s^{k-\delta}$ 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 [NW94, KI04, AGS18, KST19], our construction is purely algebraic and does not rely on the notion of combinatorial designs.