Approximating permanents and hafnians

Approximating permanents and hafnians, Discrete Analysis 2017:2, 34 pp.

The permanent per\((A)\) of an \(n\times n\) matrix \(A\) is like the determinant but without the sign changes: that is, it is the sum \(\sum_{\pi\in S_n}\prod_{i=1}^nA_{i\pi(i)}\). If \(A\) is the bipartite adjacency matrix of a bipartite graph \(G\), then per\((A)\) is the number of perfect matchings in \(G\).

Whereas row-operations allow one to compute the determinant of a matrix efficiently, computing the permanent is known, by a famous result of Valiant, to be hard (in the sense that if you could compute it efficiently, then you would be able to give efficient solutions to a wide variety of enumeration problems, and would in particular have shown that P=NP). However, another famous result, due to Jerrum, Sinclair and Vigoda, which built on earlier work of Jerrum and Sinclair, shows that there are probabilistic algorithms that run in polynomial time and approximate the permanent to within a factor \(1+\epsilon\) with high probability.

This paper concerns the question of how well the permanent can be approximated using a deterministic algorithm. The main result of this paper is that if \(\delta,\epsilon>0\) then for each \(n\in\mathbb N\) there is a polynomial \(p\) in \(n^2\) variables of degree \(O_\delta(\log n+\log(1/\epsilon))\) such that if \(A\) is any \(n\times n\) matrix with all its entries between \(\delta\) and 1, then the permanent of \(A\) can be approximated to within a factor \(1+\epsilon\) by \(\exp(p(A))\). Here, of course, \(p(A)\) is \(p\) applied to the entries of \(A\). Furthermore, \(p(A)\) can be computed in time \(n^{O_\delta(\log n+\log(1/\epsilon))}\).

As mentioned above, the permanent of a 01-matrix counts the number of perfect matchings in a bipartite graph. If instead one is interested in the number of perfect matchings in a graph with \(2n\) vertices (that is, the number of sets of \(n\) disjoint edges), then the corresponding quantity is called the hafnian. For a general \(2n\times 2n\) matrix \(A\), the hafnian haf\((A)\) is the sum over all partitions of \(\{1,\dots,2n\}\) into \(n\) sets \(\{i_r,j_r\}\) of the product \(\prod_{r=1}^nA_{i_rj_r}\).

The author proves the same result for hafnians that he obtains for permanents. This is interesting, because it is not known how to approximate hafnians even with a randomized algorithm.

The permanent and hafnian are polynomials of degree \(n\) in the matrix entries, so these results say that on the class of matrices being considered (that is, real matrices with all entries between \(\delta\) and 1), they can be approximated by polynomials of much lower degree. The proofs depend on results that say that the two polynomials cannot be zero on a complex matrix that is close to this class.

Similar results are proved for complex matrices with all their entries close to 1. In this case the methods carry over to permanents of multidimensional tensors, but multidimensional generalizations appear to be harder to obtain for the results mentioned above, for reasons explained in the paper, and are not currently known.