Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GCT CHASM:
Reports tagged with GCT chasm:
TR18-019 | 28th January 2018
Zeyu Guo, Nitin Saxena, Amit Sinhababu

#### Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint