Faster combinatorial algorithms for determinant and Pfaffian (Q848938)

The author describes a novel algebraic view of the algorithms of \textit{M. Mahajan} and \textit{V. Vinay} [in: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997); Chic. J. Theor. Comput. Sci. 1997, Article No.~5 (1997; Zbl 0924.68088)] for computing the determinant and Pfaffian of skew-symmetric matrices. This is based on a relation to a pseudo-polynomial dynamic-programming algorithm for the knapsack problem, which gives to the authors the possibility to interpret the Mahajan-Vinay algorithm as a computation of an algebraic version of this problem.