On approximability of the Permanent of PSD matrices
<|reference_start|>On approximability of the Permanent of PSD matrices: 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 $\|\cdot\|_{2\to q}$ ``norm'' problem of a matrix for all $-1 < q < 2$.<|reference_end|>
@article{ebrahimnejad2024on,
    title={On approximability of the Permanent of PSD matrices},
    author={Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan},
    journal={arXiv preprint arXiv:2404.10959},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.10959},
    primaryClass={cs.DS cs.CC}
}