Options
DERANDOMIZATION FROM ALGEBRAIC HARDNESS
Journal
SIAM Journal on Computing
ISSN
00975397
Date Issued
2022-01-01
Author(s)
Guo, Zeyu
Kumar, Mrinal
Saptharishi, Ramprasad
Solomon, Noam
Abstract
A hitting-set generator (HSG) is a polynomial map Gen: Fk → Fn such that for all n-variate polynomials C of small enough circuit size and degree, if C is nonzero, then C ◦ 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 F of characteristic zero: Let k ∈ N and δ > 0 be arbitrary constants. Suppose {Pd}d∈N is an explicit family of k-variate polynomials such that deg Pd = d and Pd requires algebraic circuits of size dδ. Then, there are explicit hitting sets of polynomial size for the class 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 30th 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 ∈ N and δ > 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δ circuits. Then there is an explicit hitting set of size 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 τ-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.
Volume
51
Publication link
Subjects