An Algorithmic Method of Partial Derivatives
15.11.2019 von 14:15 bis 15:00
We give applications of the following problem to parameterized algorithms: Given a d × d matrix A, whose entries are linear forms, and a differential operator T of degree d represented by a (skew) arithmetic circuit, decide if the partial derivative of det(A) by T vanishes. This approach leads to improvements and significant simplifications of previous parameterized algorithms for unweighted problems. This question is connected to recent approaches in parameterized algorithms involving the exterior algebra and Waring rank, and raises natural questions in commutative algebra that could yield further improvements.
This is joint work with Kevin Pratt from CMU.