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

DOI10.1145/3188745.3188792MaRDI QIDQ5230372zbMATH OpenOpenAlexFDO

Authors Amir Shpilka, Michael A. Forbes

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.09967

zbMATH Keywords

arithmetic circuitsPSPACEpolynomial identity testingexplicit constructionalgebraic circuitshitting-set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Networks and circuits as models of computation; circuit complexity (68Q06)

Abstract: In this paper we study the complexity of constructing a hitting set for the closure of 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 n-tuples over the rationals 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.

Recommendations

• scientific article; zbMATH DE number 7009617
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Near-optimal bootstrapping of hitting sets for algebraic circuits
• Hitting sets for orbits of circuit classes and polynomial families
• Quasipolynomial hitting sets for circuits with restricted parse trees
• A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3
• scientific article; zbMATH DE number 7250150
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• A \#SAT algorithm for small constant-depth circuits with PTF gates

Cited in

(11)

• scientific article; zbMATH DE number 7250150 (Why is no real title available?)
• A note on VNP-completeness and border complexity
• Variety evasive subspace families
• Near-optimal bootstrapping of hitting sets for algebraic models
• Algebraic dependencies and \(\mathsf{PSPACE}\) algorithms in approximative complexity over any field
• Near-optimal bootstrapping of hitting sets for algebraic circuits
• Blackbox identity testing for sum of special ROABPs and its border class
• Complete decomposition of symmetric tensors in linear time and polylogarithmic precision
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)

This page was built for publication: A PSPACE construction of a hitting set for the closure of small algebraic circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230372)