## 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.