Computing permanents of complex diagonally dominant matrices and tensors

2018/01/12 by Alexander Barvinok, Barvinok, Alexander
Computer Science · Mathematics · #05C65 #15A15 #41A10 #68R05 #68W25 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO #msc:05C65 #msc:15A15 #msc:41A10 #msc:68R05 #msc:68W25

paper · pdf · doi:10.48550/arxiv.1801.04191

13 pages, minor improvements

arxiv created 2018/09/11 · arxiv updated 2018/09/13

Abstract

We prove that for any λ> 1, fixed in advance, the permanent of an n × 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.

Related

• Computing the permanent of (some) complex matrices
• On evaluation of permanents
• Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices
• An upper bound for permanents of nonnegative matrices
• An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality