# Approximating permanents and hafnians

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2016.

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

- [Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers](https://mlsanity.com/paper/2409.04320/) (2024)

## Abstract (arXiv)

We prove that the logarithm of the permanent of an nxn real matrix A and the logarithm of the hafnian of a 2nx2n real symmetric matrix A can be approximated within an additive error 1 > epsilon > 0 by a polynomial p in the entries of A of degree O(ln n - ln epsilon) provided the entries a_ij of A satisfy delta < a_ij < 1 for an arbitrarily small delta > 0, fixed in advance. Moreover, the polynomial p can be computed in n^{O(ln n - ln epsilon)} time. We also improve bounds for approximating ln per A, ln haf A and logarithms of multi-dimensional permanents for complex matrices and tensors A.