2017/12/28 by Michael A. Forbes, Forbes, Michael A., Shpilka, Amir
Computer Science · #Algebraic Geometry (math.AG) #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1712.09967
openalex publication_date 2017/12/28 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
In this paper we study the complexity of constructing a hitting set for the\nclosure of VP, the class of polynomials that can be infinitesimally\napproximated by polynomials that are computed by polynomial sized algebraic\ncircuits, over the real or complex numbers. Specifically, we show that there is\na PSPACE algorithm that given n,s,r in unary outputs a set of n-tuples over the\nrationals of size poly(n,s,r), with poly(n,s,r) bit complexity, that hits all\nn-variate polynomials of degree-r that are the limit of size-s algebraic\ncircuits. Previously it was known that a random set of this size is a hitting\nset, but a construction that is certified to work was only known in EXPSPACE\n(or EXPH assuming the generalized Riemann hypothesis). As a corollary we get\nthat a host of other algebraic problems such as Noether Normalization Lemma,\ncan also be solved in PSPACE deterministically, where earlier only randomized\nalgorithms and EXPSPACE algorithms (or EXPH assuming the generalized Riemann\nhypothesis) were known.\n The proof relies on the new notion of a robust hitting set which is a set of\ninputs such that any nonzero polynomial that can be computed by a polynomial\nsize algebraic circuit, evaluates to a not too small value on at least one\nelement of the set. Proving the existence of such a robust hitting set is the\nmain technical difficulty in the proof.\n Our proof uses anti-concentration results for polynomials, basic tools from\nalgebraic geometry and the existential theory of the reals.\n