Computing permanents of complex diagonally dominant matrices and tensors

Abstract

We prove that for any $\lambda >1$, fixed in advance, the permanent of an $n\times n$ complex matrix, where the absolute value of each diagonal entry is at least $\lambda$ 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<\epsilon <1$ in quasi-polynomial $n^{O(\ln n-\ln \epsilon )}$ 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