Hyperpfaffians and Geometric Complexity Theory

2019/12/19 by Christian Ikenmeyer, Ikenmeyer, Christian, Michael Walter +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Commutative Algebra and Its Applications #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1912.09389

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.

Cited by

• Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency

Related

• The Complexity of Tensor Rank
• How hard is the tensor rank?
• An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP
• Padded polynomials, their cousins, and geometric complexity theory
• On the complexity of finding tensor ranks