A matrix X is called a linear matrix if all its entries are affine forms. Given oracle access to w2 degree d polynomials in n variables that are entries of a w × w matrix F, we wish to compute a factorization of F as a product of linear matrices, if such a factorization exists. Finding such a representation is closely related to finding an optimal way to compute a given polynomial via an algebraic branching program. Over rationals and finite fields of sufficiently large characteristic, we give a poly(n,d,b) time randomized algorithm to compute such a factorization in the average-case, when w ≤ √n/2. Here b is the bit length of the coefficients of the polynomials in F. Over finite fields the output of our algorithm is over the base field, whereas over ℚ the output is over a small extension of ℚ. Our algorithm actually gives an efficient worst-case randomized reconstruction algorithm for pure matrix products (which is a non-degeneracy notion that we define in this work). Additionally, we show that if we are given just one entry of F then we can recover a suitable factorization in poly(dw3,n,b) time.
This is joint work with Neeraj Kayal, and Chandan Saha.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
