אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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 nxn matrix whose entries are themselves 2x2 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 dxd 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).

This is joint work with Steve Chien, Alistair Sinclair and Srikanth Srinivasan.