Computer Science/Discrete Mathematics Seminar III

All known efficient algorithms for computing the determinant of a matrix rely on commutativity of the matrix entries. How important is this property, and could we make use of an algorithm that computes determinants without assuming commutativity? In this talk I will discuss both aspects of this question: 1. If we could efficiently compute the determinant over a sufficiently rich lass of non-commutative algebras, then we would get an extremely simple and efficient approximation scheme for the permanent of a 0-1 matrix. 2. The algebraic branching program complexity of the determinant over almost any non-commutative algebra is exponentially large. If one is a pessimist, these results suggest that non-commutative determinant computation would be nice but is hopelessly hard. If one is an optimist, they represent a challenge to devise a new approximation scheme for the permanent. Joint work with Steve Chien and Lars Rasmussen.