Computing permanents of complex diagonally dominant matrices and tensors

January 12, 2018 ยท The Ethereal ยท ๐Ÿ› Israel Journal of Mathematics

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Alexander Barvinok arXiv ID 1801.04191 Category math.CO: Combinatorics Cross-listed cs.DM, cs.DS Citations 11 Venue Israel Journal of Mathematics Last Checked 6 months ago
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago