Computer Science/Discrete Mathematics Seminar I

I will talk about the computational complexity of computing the noncommutative determinant. In contrast to the case of commutative algebras, we know of (virtually) no efficient algorithms to compute the determinant over non-commutative domains. Our results show that the determinant in noncommutative settings can be as hard as the permanent. We will consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. We show that if the noncommutative determinant polynomial has small noncommutative arithmetic circuits, then so does the noncommutative permanent. Consequently, the commutative permanent polynomial has small commutative arithmetic circuits. Then, time permitting, we will consider the complexity of computing the noncommutative determinant over specific noncommutative algebras and show that, even for 2-dimensional matrix algebras, this problem remains as hard as computing the permanent. Based on joint work with V Arvind and Steve Chien.