Almost Settling the Hardness of Noncommutative Determinant

by Steve Chien, Prahladh Harsha, Alistair Sinclair and Srikanth Srinivasan.

Oded's comments

The two conflicting results (i.e., hard vs easy) as summarized in the first part of the 2nd paragraph, speak for themselves. The third result (i.e., dichotomy) identifies a parameter of algebras that governs the complexity of computing the determinant of matrices over these algebras.

The original abstract

The determinant and the permanent of a matrix, though deceivingly similar in their definitions, behave very differently with respect to how efficiently one can compute these quantities. The determinant of a matrix over a field can be easily computed via Gaussian elimination 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 ``over which algebras, is the determinant easier to compute than the permament?" Furthermore, since all algorithms for determinant crucially use commutivity of the underlying algebra, we could ask ``is commutativity essential for efficient determinant computation?"

Extending the recent result of Arvind and Srinivasan [STOC 2010], we show that computing the determinant of an $n\times n$ matrix whose entries are themselves $2\times 2$ matrices over a field is as hard as computing the permanent over the field. On the other hand, surprisingly if one restricts the elements to be $d\times d$ upper triangular matrices, then determinant can be computed in $poly(n^d)$ time. Combining this with the decomposition theorem of finite algebras, we get the following dichotomy result: if $A$ is a constant dimensional algebra over a finite field of odd characteristic, then the commutativity of the quotient algebra $A/R(A)$ determines efficient determinant computation (where $R(A)$ is the radical of $A$).

Back to list of Oded's choices.