Consider a square m x m matrix M whose entries are polynomials in n variables x1,x2,..,xn over a field F. We want to compute the rank of this matrix M over the rational function field F(x1,x2,...,xn). If the entries of M are linear polynomials then computation of rank of M is equivalent to the polynomial identity testing (of algebraic branching programs). So we have trivial randomized polynomial time algorithms for this problem. But a deterministic polynomial time algorithm remains elusive. Therefore it is reasonable to ask whether one can approximate the rank of M in deterministic polynomial time. A deterministic PTAS for the rank of M (when the entries of M are linear polynomials) was given in BJP17.
In this work we consider the matrices M whose entries are constant degree polynomials. One again wants to compute the rank of M over the rational function field F(x1,x2,...,xn). This can be used to compute the transcendence degree of any set of constant degree polynomials by using the Jacobian criterion. We describe a deterministic PTAS for the rank of M (when the entries of M are constant degree polynomials). This naturally generalizes the results of BJP17.
This is based on joint work with Vishwas Bhargava (Rutgers University), Markus Bläser (Saarland University) and Anurag Pandey (Max-Planck-Institut für Informatik).
[BJP17] : Markus Bläser, Gorav Jindal, and Anurag Pandey. Greedy strikes again: A deterministic PTAS for commutative rank of matrix spaces. In Proc. 32nd IEEE Conf. on Computational Complexity (CCC'17), volume 79 of LIPIcs, pages 33:1-33:16. IEEE Comp. Soc. Press, 2017. |