๐ฎ
๐ฎ
The Ethereal
Computing permanents of complex diagonally dominant matrices and tensors
January 12, 2018 ยท The Ethereal ยท ๐ Israel Journal of Mathematics
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal