TY - GEN

T1 - A PSPACE construction of a hitting set for the closure of small algebraic circuits

AU - Forbes, Michael A.

AU - Shpilka, Amir

N1 - Publisher Copyright:
© 2018 Copyright held by the owner/author(s).

PY - 2018/6/20

Y1 - 2018/6/20

N2 - In this paper we study the complexity of constructing a hitting set for VP, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given n, s, r in unary outputs a set of inputs from Qn of size poly(n, s, r), with poly(n, s, r) bit complexity, that hits all n-variate polynomials of degree r that are the limit of size s algebraic circuits. Previously it was known that a random set of this size is a hitting set, but a construction that is certified to work was only known in EXPSPACE (or EXPH assuming the generalized Riemann hypothesis). As a corollary we get that a host of other algebraic problems such as Noether Normalization Lemma, can also be solved in PSPACE deterministically, where earlier only randomized algorithms and EXPSPACE algorithms (or EXPH assuming the generalized Riemann hypothesis) were known. The proof relies on the new notion of a robust hitting set which is a set of inputs such that any nonzero polynomial that can be computed by a polynomial size algebraic circuit, evaluates to a not too small value on at least one element of the set. Proving the existence of such a robust hitting set is the main technical difficulty in the proof. Our proof uses anti-concentration results for polynomials, basic tools from algebraic geometry and the existential theory of the reals.

AB - In this paper we study the complexity of constructing a hitting set for VP, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given n, s, r in unary outputs a set of inputs from Qn of size poly(n, s, r), with poly(n, s, r) bit complexity, that hits all n-variate polynomials of degree r that are the limit of size s algebraic circuits. Previously it was known that a random set of this size is a hitting set, but a construction that is certified to work was only known in EXPSPACE (or EXPH assuming the generalized Riemann hypothesis). As a corollary we get that a host of other algebraic problems such as Noether Normalization Lemma, can also be solved in PSPACE deterministically, where earlier only randomized algorithms and EXPSPACE algorithms (or EXPH assuming the generalized Riemann hypothesis) were known. The proof relies on the new notion of a robust hitting set which is a set of inputs such that any nonzero polynomial that can be computed by a polynomial size algebraic circuit, evaluates to a not too small value on at least one element of the set. Proving the existence of such a robust hitting set is the main technical difficulty in the proof. Our proof uses anti-concentration results for polynomials, basic tools from algebraic geometry and the existential theory of the reals.

KW - Algebraic circuits

KW - Arithmetic circuits

KW - Explicit construction

KW - Hitting-set

KW - PSPACE

KW - Polynomial identity testing

UR - http://www.scopus.com/inward/record.url?scp=85049921832&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049921832&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188792

DO - 10.1145/3188745.3188792

M3 - Conference contribution

AN - SCOPUS:85049921832

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 87

EP - 99

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -