Speaker:
Alistair Sinclair, UC Berkeley
Title:
Permanents, Determinants and Commutativity
Abstract:
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 we 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, we 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 we will show that
computing the determinant over “most” non-commutative algebras is as hard as
computing the permanent exactly. In fact, we 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.)