Hyperpfaffians and Geometric Complexity Theory

Authors Christian Ikenmeyer, Michael Walter

Publication date 19 December 2019

Actions of groups on commutative rings; invariant theory (13A50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

Abstract: The hyperpfaffian polynomial was introduced by Barvinok in 1995 as a natural generalization of the well-known Pfaffian polynomial to higher order tensors. We prove that the hyperpfaffian is the unique smallest degree SL-invariant on the space of higher order tensors. We then study the hyperpfaffian's computational complexity and prove that it is VNP-complete. This disproves a conjecture of Mulmuley in geometric complexity theory about the computational complexity of invariant rings.

This page was built for publication: Hyperpfaffians and Geometric Complexity Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6331461)