We consider the special class of ideals where each generator is a univariate pi over the variable xi. First we show a randomized O(dr poly(n)) algorithm for testing if a rank r polynomial is in a univariate ideal or not.
In a special case this lends itself to an algorithm for computing the Permanent of a matrix of rank r which works over all fields and generalizes a result of Barvinok. Next we discuss a result of Glynn that states that the Permanent of an n×n matrix of rank r is 0 modulo p when p<n/r and we prove a a more general theorem.
When the univariate ideal has only repeated roots we show a randomized O∗(4.08d) algorithm where d is the degree of the input polynomial. When the generators of the ideal have distinct roots and the input polynomial is a depth 3 circuit we show a deterministic O∗(4d) algorithm where d is the degree of the input polynomial.
This is based on joint work with V. Arvind, Partha Mukhopadhyay and Abhranil Chatterjee.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
