On approximability of the Permanent of PSD matrices

We study the complexity of approximating the permanent of a positive semidefinite matrix A∈ mathbbCn× n. 1. We design 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 [AGOS17,YP22]. Here, γ ≈ 0.577 is Euler's constant. 2. 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.