On approximability of the Permanent of PSD matrices

Abstract

We study the complexity of approximating the permanent of a positive semidefinite matrix $A\in {\mathbb{C}}^{n\times n}$. 1. We design a new approximation algorithm for $\mathrm{per}(A)$ with approximation ratio $e^{(0.9999+\gamma )n}$, exponentially improving upon the current best bound of $e^{(1+\gamma -o(1))n}$ [AGOS17,YP22]. Here, $\gamma \approx 0.577$ is Euler's constant. 2. We prove that it is NP-hard to approximate $\mathrm{per}(A)$ within a factor $e^{(\gamma -\epsilon )n}$ for any $\epsilon >0$. This is the first exponential hardness of approximation for this problem. Along the way, we prove optimal hardness of approximation results for the $\Vert \cdot {\Vert }_{2\to q}$ ``norm'' problem of a matrix for all $-1<q<2$.