On approximability of the Permanent of PSD matrices

Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan

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}…