An Algorithmic Method of Partial Derivatives

Abstract

We study the following problem and its applications: given a homogeneous degree-$d$ polynomial $g$ as an arithmetic circuit, and a $d\times d$ matrix $X$ whose entries are homogeneous linear polynomials, compute $g(\partial /\partial x_1,\dots ,\partial /\partial x_n)\det X$. By considering special cases of this problem we obtain faster parameterized algorithms for several problems, including the matroid $k$-parity and $k$-matroid intersection problems, faster \emph{deterministic} algorithms for testing if a linear space of matrices contains an invertible matrix (Edmonds's problem) and detecting $k$-internal outbranchings, and more. We also match the runtime of the fastest known deterministic algorithm for detecting subgraphs of bounded pathwidth, while using a new approach. Our approach raises questions in algebraic complexity related to Waring rank and the exponent of matrix multiplication $\omega$. In particular, we study a new complexity measure on the space of homogeneous polynomials, namely the bilinear complexity of a polynomial's apolar algebra. Our algorithmic improvements are reflective of the fact that for the degree-$n$ determinant polynomial this quantity is at most $O(n{2}^{\omega n})$, whereas all known upper bounds on the Waring rank of this polynomial exceed $n!$.