Computing permanents of complex diagonally dominant matrices and tensors

Abstract

We prove that for any $λ> 1$, fixed in advance, the permanent of an $n \times n$ complex matrix, where the absolute value of each diagonal entry is at least $λ$ times bigger than the sum of the absolute values of all other entries in the same row, can be approximated within any relative error $0 < ε< 1$ in quasi-polynomial $n^{O(\ln n - \ln ε)}$ time. We extend this result to multidimensional permanents of tensors and discuss its application to weighted counting of perfect matchings in hypergraphs.

13 pages, minor improvements