# On approximability of the Permanent of PSD matrices

arXiv: https://arxiv.org/abs/2404.10959 · HTML: https://mlsanity.com/paper/2404.10959/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2024.

## Built on by (most cited first, 1 of 1)

- [Towards a Law of Iterated Expectations for Heuristic Estimators](https://mlsanity.com/paper/2410.01290/) (2024)

## Abstract (arXiv)

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.