A remark on approximating permanents of positive definite matrices

2020/05/13 by Alexander Barvinok, Barvinok, Alexander
Computer Science · Mathematics · #15A15 #15A57 #26B25 #60J22 #68W20 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #cs.DS #math.CO #msc:15A15 #msc:15A57 #msc:26B25 #msc:60J22 #msc:68W20

paper · pdf · doi:10.48550/arxiv.2005.06344

5 pages

arxiv created 2020/05/13 · arxiv updated 2020/05/14

Abstract

Let A be an n × n positive definite Hermitian matrix with all eigenvalues between 1 and 2. We represent the permanent of A as the integral of some explicit log-concave function on \Bbb R²ⁿ. Consequently, there is a fully polynomial randomized approximation scheme (FPRAS) for the permanent of A.

Related

• FPRAS Approximation of the Matrix Permanent in Practice
• A simple polynomial time algorithm to approximate the permanent within a simply exponential factor
• Approximating the Permanent of a Random Matrix with Vanishing Mean
• Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
• An upper bound for permanents of nonnegative matrices