Permanents, Determinants and Non-Commutativity
| SPECIAL TALK: COMPUTER SCIENCE/DISCRETE MATH III | |
| Topic: | Permanents, Determinants and Non-Commutativity |
| Speaker: | Alistair Sinclair |
| 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.