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.