Derandomization from Algebraic Hardness
Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon · SIAM Journal on Computing · 2022
A hitting-set generator (HSG) is a polynomial map ${{\mathsf{Gen}}}:{\mathbb{F}}^k \to {\mathbb{F}}^n$ such that for all $n$-variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ {{\mathsf{Gen}}}$ 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 ${\mathbb{F}}$ of characteristic zero: Let $k\in {\mathbb{N}}$ and $\delta > 0$ be arbitrary constants. Suppose ${\left\{ {P_d} \right\}}_{d\in {\mathbb{N}}}$ is an explicit family of $k$-variate polynomials such that $\deg P_d = d$ and $P_d$ requires algebraic circuits of size $d^\delta$. Then, there are explicit hitting sets of polynomial size for the class ${\mathsf{VP}}$. 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 [N. Nisan and A. Wigderson, J. Comput. System Sci., 49 (1994), pp. 149--167; V. Kabanets and R. Impagliazzo, Comput. Complexity, 13 (2004), pp. 1--46; M. Agrawal, S. Ghosh, and N.Saxena, Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 8107--8118; M. Kumar, R. Saptharishi, and A. Tengse, Proceedings of the \textup30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 639--646], 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\in {\mathbb{N}}$ and $\delta > 0$ be arbitrary constants. 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^\delta$ circuits. Then there is an explicit hitting set of size ${\operatorname{poly}}(s)$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits. As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $\tau$-conjecture of Shub and Smale [M. Shub and S. Smale, Duke Math. J., 81 (1995), pp. 47--54; S. Smale, Math. Intelligencer, 20 (1998), pp. 7--15] is true.