Permanents, Determinants and Commutativity

The permanent and determinant of a matrix, while syntactically very similar, are computationally very different: as is well known, there are a number of efficient algorithms for computing the determinant, but the permanent is #P-hard and hence presumably intractable. It is a long-standing challenge in theoretical computer science to explain this phenomenon. In this talk I will focus on one aspect of this question, namely the role played by commutativity of the matrix entries. (Known algorithms for computing determinants all apparently rely crucially on commutativity.) On the one hand, I will show that the ability to compute the determinant over certain non-commutative algebras would lead to a very simple and efficient approximation algorithm for the permanent. This serves as motivation for the second part of the talk, in which I will show that computing the determinant over “most” non-commutative algebras is as hard as computing the permanent exactly. In fact, I will give a dichotomy theorem for efficient computation of the determinant over non-commutative algebras in terms of a structural property of the algebras.

Based on joint work with --- in various combinations --- Steve Chien, Praladh Harsha, Lars Rasmussen, and Srikanth Srinivasan.