Approximating permanents and hafnians
From MaRDI portal
Publication:4645007
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.
Recommendations
- Approximating the -permanent
- Approximating the permanent: A simple approach
- Approximating the permanent via nonabelian determinants
- Approximation theorems for random permanents and associated stochastic processes
- Publication:3033320
- Approximating the permanent of graphs with large factors
- Research problems
- scientific article; zbMATH DE number 1354921
- On the complexity of approximating the Hadwiger number
Cites work
- scientific article; zbMATH DE number 5485444 (Why is no real title available?)
- scientific article; zbMATH DE number 3621932 (Why is no real title available?)
- scientific article; zbMATH DE number 3260031 (Why is no real title available?)
- A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- An asymptotic approximation for the permanent of a doubly stochastic matrix
- An efficient tree decomposition method for permanents and mixed discriminants
- An upper bound on the number of high-dimensional permutations
- Approximating permanents of complex matrices
- Benjamini-Schramm continuity of root moments of graph polynomials
- Computing the partition function for cliques in a graph
- Computing the partition function for graph homomorphisms with multiplicities
- Computing the partition function for perfect matchings in a hypergraph
- Computing the permanent of (some) complex matrices
- Concentration of permanent estimators for certain large matrices.
- Counting independent sets up to the tree threshold
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Fast convergence of the Glauber dynamics for sampling independent sets
- Hafnians, perfect matchings and Gaussian matrices
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Matching theory
- Mathematical Foundations of Computer Science 2005
- Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
- The Lee‐Yang and Pólya‐Schur programs. II. Theory of stable polynomials and applications
- The Zeros of the Partial Sums of the Exponential Series
- The complexity of computing the permanent
- The computational complexity of linear optics
- The quantum computer puzzle
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- The roots of the independence polynomial of a clawfree graph
- Theory of monomer-dimer systems
- Two Algorithmic Results for the Traveling Salesman Problem
- Zero-free regions of partition functions with applications to algorithms and graph limits
Cited in
(12)- On Bobkov's approximate de Finetti representation via approximation of permanents of complex rectangular matrices
- A novel approach to perturbative calculations for a large class of interacting boson theories
- Computing the permanent of (some) complex matrices
- Computing permanents of complex diagonally dominant matrices and tensors
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
- On a conjecture of Sokal concerning roots of the independence polynomial
- Hafnians, perfect matchings and Gaussian matrices
- Angle-restricted sets and zero-free regions for the permanent
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Pfaffians, Hafnians and products of real linear functionals
- Spectral independence via stability and applications to Holant-type problems
This page was built for publication: Approximating permanents and hafnians
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645007)
