Almost Settling the Hardness of Noncommutative Determinant

respect to how efficiently one can compute these quantities. The determinant of a matrix over a field or any commutative ring can be easily computed while computing the permanent, as shown by Valiant, is at least as hard as counting the number of satisfiable
assignments to a Boolean formula. Given this, it is natural to ask "what makes the determinant easier to compute than the
permament?, Is commutativity essential for efficient determinant computation?"

In this talk, I'll show that computing the determinant of an nxn matrix whose entries are themselves 2x2 matrices over a field is as hard as computing the permanent over the field (this strengthens the recent result of Arvind and Srinivasan). Combining this with
the decomposition theorem of finite algebras, we get the following dichotomy result: if A is a finite dimensional algebra over a finite
field, then the commutativity of A/R(A) determines efficient determinant computation (where R(A) is the radical of A).

Joint work with Steve Chien, Alistair Sinclair and Srikanth Srinivasan. (See: http://arxiv.org/abs/1101.1169)