Speaker
Description
Resolving a long-standing open question, we show that that the core AD problem of accumulating a Jacobian matrix while minimizing multiplications is NP-complete. Complementing this, we show that the running time of a relatively straight-forward $O^*(2^n)$ algorithm is essentially best possible under the Exponential Time Hypothesis. We also establish NP-completeness for the 'scarcity' problem of obtaining a minimum-size matrix-free Jacobian representation.
Importantly, we formulate both problems graph-theoretically, using sequences of vertex eliminations in a directed acyclic graph. Our results are facilitated by several illustrative structural insights about sequences of vertex eliminations, which also lead to a novel SAT encoding for Jacobian accumulation. We conclude with a discussion of open problems related to parameterized algorithms, approximations, and problem variants allowing edge eliminations. In addition to sharing our results, we hope to instigate more collaboration between graph algorithms researchers and the AD community.