Approximating the Permanent via Nonabelian Determinants
Alexander Russell, UConn
Tuesday, 7 April 2009
Room 140, Computer Science Building
Since the celebrated work of Jerrum, Sinclair, and Vigoda, we have known that the permanent of a 0-1 matrix can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has asked whether there is an alternate polynomial-time approximation scheme which is purely algebraic. These schemes work by replacing each 1 with a random element of an algebra A, and considering the determinant of the resulting matrix.
In the case where A is noncommutative, this determinant can be defined in several ways. We address a conjecture of Barvinok regarding his symmetrized determinant, showing that when A is a d-dimensional matrix algebra the resulting estimator has small variance when d is large enough. We also study the unsymmetrized determinant, generalizing recent results of Chien, Rasmussen, and Sinclair on the Clifford group to matrix algebras in general.
However, our results do not provide a new polynomial-time approximation scheme for the permanent. Ironically, they suggest that the symmetrized determinant---which we can compute in polynomial time for constant d---gives poorer estimators than the unsymmetrized determinant, for which no efficient algorithm is known.
We obtain these results using diagrammatic techniques in which we write matrix products as contractions of tensor products. When these matrices are random, in either the Haar measure or the Gaussian measure, we can evaluate the trace of these products in terms of the cycle structure of a random permutation. In the symmetrized case, we also use ideas from the representation theory of the symmetric group.
Last modified 11 May 2009