|SPECIAL TALK: COMPUTER SCIENCE/DISCRETE MATH III|
|Topic:||Permanents, Determinants and Non-Commutativity|
|Affiliation:||Computer Science Division, University of California, Berkeley|
|Date:||Wednesday, December 13|
|Time/Room:||11:15am - 12:30pm/West Building Lecture Theatre|
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.