论文标题
部分衍生物的算法方法
An Algorithmic Method of Partial Derivatives
论文作者
论文摘要
我们研究以下问题及其应用：给定同质度 - $ d $多项式$ g $作为算术电路，以及$ d \ times d $矩阵$ x $，其条目是同质的线性多项式，计算$ g（\ partial/\ partial/\ partial x_1，\ ldots，\ ldots，\ ldots，\ partial x______________通过考虑此问题的特殊情况，我们可以获得更快的参数化算法，包括多个问题，包括Matroid $ k $ - PARITY和$ K $ -MATROID相交问题，更快的\ emph {确定性}算法用于测试用于矩阵的线性空间是否包含可转让的Matrix（Edmonds Extrix and）$ k的$ k $ KIND $ KIND $ KIND $ KIND $ KIND，我们还使用新方法时，我们还匹配用于检测有界路径的子图的最快已知确定性算法的运行时。 我们的方法提出了与Waring等级有关的代数复杂性和矩阵乘法$ω$的指数的问题。特别是，我们研究了关于均质多项式空间的新复杂度度量，即多项式的Algebra的双线性复杂性。我们的算法改进反映了以下事实：对于$ n $ n $ n $多项式，该数量最多是$ o（n 2^{ωn}）$，而该多项式的所有已知上限超过$ n！$。
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, \ldots, \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 $ω$. 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^{ωn})$, whereas all known upper bounds on the Waring rank of this polynomial exceed $n!$.
