Permanent estimators via random matrices

The permanent of a square matrix is defined similarly to the determinant. It is the sum of products of entries over all ``generalized diagonals'', only without signs in front of the products. The evaluation of the determinant is computationally efficient, while the evaluation of the permanent is an NP-hard problem. Since the deterministic methods are not available, permanents are estimated probabilistically. One of such estimators constructed by Barvinok evaluates the permanent of a deterministic matrix via the determinant of a random matrix associated to it. Barvinok proved that the multiplicative error of this estimator is at most exponential, and this result cannot be improved for general matrices. We provide conditions on the matrix, under which the Barvinok estimator yields a subexponential error.

Joint work with Ofer Zeitouni.