For a matrix with entries given by multivariate polynomials (over a field F) of degrees bounded by a constant d, a problem of interest is to find its rank over F(x1,…,xn). The problem seems to be of fundamental nature, as it generalizes several computational problems arising in algebra, geometry, and combinatorics. For instance, when the entries are given by homogeneous linear forms, this rank computation problem already captures the problems like testing for perfect matching in graphs, and identity testing for algebraic branching programs. Its higher degree cases capture more general problems of algebro-geometric nature, like testing algebraic independence of polynomials using the Jacobian matrix, and finding the dimension of the dual varieties of hypersurfaces using the Hessian matrix.
Although the problem has a simple and efficient randomized algorithm using the Schwartz-Zippel lemma, an efficient deterministic computation of the rank is a major open problem, since a deterministic algorithm for exactly computing the rank in the linear case is already equivalent to the celebrated Polynomial Identity Testing (PIT) problem which itself would imply circuit complexity lower bounds (Kabanets-Impagliazzo ’03).
In this talk, we will see a simple deterministic algorithm for computing the rank up to a factor of (1 – ε), which runs in polynomial time (i.e. we give a PTAS) when ε and d are constants.
Joint work with Vishwas Bhargava, Markus Bläser, and Gorav Jindal.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
