Abstract
Testing whether a set F of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). In this work we put the problem in AM & coAM. In particular, dependence testing is unlikely to be NP-hard. Our proof method is algebro-geometric-- estimating the size of the image/preimage of the polynomial map F over the finite field. A gap in this size is utilized in the AM protocols. Next, we introduce a new problem called *approximate* polynomials satisfiability (APS). We show that APS is NP-hard and, using projective algebraic-geometry ideas, we put APS in PSPACE (prior best was EXPSPACE via Grobner bases). This has many unexpected applications to approximative complexity theory. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017); greatly mitigating the GCT Chasm (exponentially in terms of space complexity).