Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-135 | 14th September 2023 13:47

On Annihilators of Explicit Polynomial Maps


Authors: Prerona Chatterjee, Anamay Tengse
Publication: 14th September 2023 23:28
Downloads: 160


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.

ISSN 1433-8092 | Imprint