Theory of Computing
-------------------
Title     : Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field
Authors   : Zeyu Guo, Nitin Saxena, and Amit Sinhababu
Volume    : 15
Number    : 16
Pages     : 1-30
URL       : https://theoryofcomputing.org/articles/v015a016

Abstract
--------

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic
dependence is a basic problem with several applications. The
polynomials are given as algebraic circuits. The complexity of
algebraic independence testing is wide open over finite fields (Dvir,
Gabizon, Wigderson, FOCS'07). Previously, the best complexity bound
known was  NP^{#P} (Mittmann, Saxena, Scheiblechner, Trans. AMS 2014).
In this article we put the problem in  AM \cap coAM.  In particular, 
dependence testing is unlikely to be  NP-hard. Our proof uses methods 
of algebraic geometry. We estimate the size of the image and the sizes 
of the preimages of the polynomial map  f  over the finite field. 
A _gap_ between the corresponding sizes for independent and for 
dependent sets of polynomials is utilized in the  AM  protocols.

Next, we study the open question of testing whether every annihilator
of  f  has zero constant term (Kayal, CCC'09). We introduce a new 
problem called _approximate polynomial satisfiability_ (APS),
which is equivalent to the preceding question by a classical
characterization in terms of the Zariski closure of the image of  f.
We show that APS is NP-hard and, using ideas from algebraic geometry, 
we put APS in PSPACE. (The best previous bound was EXPSPACE via Grobner 
basis computation.) As an unexpected application of this to approximative
complexity theory we obtain that, over _any_ field, hitting sets for 
$\overline{VP}$ can be constructed in PSPACE. This solves an open problem 
posed in (Mulmuley, FOCS'12, J.AMS 2017), greatly mitigating the GCT Chasm 
(exponentially in terms of space complexity).