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. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

Guo, Saxena, and Sinhababu (TOC'18, CCC'18) defined a natural, approximative analog of the polynomial system satisfiability problem, which they called approximate polynomial satisfiability (APS). They proved algebraic and geometric properties of it and showed an NP-hardness lower bound and a PSPACE upper bound for it. They further established how the ... more >>>