ECCC-Report TR23-135https://eccc.weizmann.ac.il/report/2023/135Comments and Revisions published for TR23-135en-usThu, 14 Sep 2023 23:28:50 +0300
Paper TR23-135
| On Annihilators of Explicit Polynomial Maps |
Prerona Chatterjee,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2023/135We 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.Thu, 14 Sep 2023 23:28:50 +0300https://eccc.weizmann.ac.il/report/2023/135