On Approximability of the Permanent of PSD Matrices

We study the complexity of approximating the permanent of a positive semidefinite matrix A∈ ℂn× n. Our first result is a new approximation algorithm for per(A) with approximation ratio e−(0.9999 + γ)n, exponentially improving upon the current best bound of e−(1+γ−o(1))n (Anari-Gurvits-Oveis Gharan-Saberi 2017, Yuan-Parrilo 2022). Here, γ ≈ 0.577 is Euler’s constant. Our second result is a hardness result. We prove that it is NP-hard to approximate per(A) within a factor e−(γ−)n for any >0. This is the first exponential hardness of approximation for this problem. Along the way, we prove optimal hardness of approximation results for the ||·||2→ q “norm” problem of a matrix for all −1 < q < 2.