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.