Approximating permanents and hafnians
arXiv:1601.07518
Abstract
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.
The article number (for "Discrete Analysis") is corrected
References in corpus (6)
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Gaussian Noise Sensitivity and BosonSampling
- Concentration of permanent estimators for certain large matrices
- The Quantum Computer Puzzle (Expanded Version)
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Computing the Independence Polynomial: from the Tree Threshold down to the Roots
Cited by in corpus (5)
- Quantum Experiments and Graphs II: Quantum Interference, Computation and State Generation
- On a conjecture of Sokal concerning roots of the independence polynomial
- The Quantum Computer Puzzle (Expanded Version)
- A novel approach to perturbative calculations for a large class of interacting boson theories
- Zero-free regions of partition functions with applications to algorithms and graph limits