TR23-135 Authors: Prerona Chatterjee, Anamay Tengse

Publication: 14th September 2023 23:28

Downloads: 243

Keywords:

We study the algebraic complexity of annihilators of polynomials maps. In particular, when a polynomial map is `encoded by' a small algebraic circuit, we show that the coefficients of an annihilator of the map can be computed in PSPACE. Even when the underlying field is that of reals or complex numbers, an analogous statement is true. We achieve this by using the class VPSPACE, that coincides with computability of coefficients in PSPACE over integers.

As a consequence, we derive the following two conditional results. First, we show that a VP-explicit hitting set generator for ''all of'' VP would separate either VP from VNP, or non-uniform P from PSPACE. Second, in relation to algebraic natural proofs, we show that proving an algebraic natural proofs barrier would imply either VP $\neq$ VNP or DSPACE($\log^{\log^{\ast}n} n$) $\not\subset$ P.