Approximating permanents and hafnians

DOI10.19086/DA.1244zbMATH Open1404.15008arXiv1601.07518OpenAlexW2963958955WikidataQ56806482 ScholiaQ56806482MaRDI QIDQ4645007FDOQ4645007

Authors: Alexander Barvinok 

Publication date: 9 January 2019

Published in: Discrete Analysis (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1601.07518

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

Mathematics Subject Classification ID

Approximation algorithms (68W25) Determinants, permanents, traces, other special matrix functions (15A15) Approximation by polynomials (41A10)

Cites Work

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Theory of monomer-dimer systems
• The complexity of computing the permanent
• Matching theory
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Counting independent sets up to the tree threshold
• The Lee‐Yang and Pólya‐Schur programs. II. Theory of stable polynomials and applications
• An upper bound on the number of high-dimensional permutations
• Two Algorithmic Results for the Traveling Salesman Problem
• Title not available (Why is that?)
• A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
• Computing the permanent of (some) complex matrices
• Computing the partition function for perfect matchings in a hypergraph
• The computational complexity of linear optics
• Approximating permanents of complex matrices
• Computing the partition function for cliques in a graph
• Title not available (Why is that?)
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Mathematical Foundations of Computer Science 2005
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• The roots of the independence polynomial of a clawfree graph
• Fast convergence of the Glauber dynamics for sampling independent sets
• Concentration of permanent estimators for certain large matrices.
• Hafnians, perfect matchings and Gaussian matrices
• Title not available (Why is that?)
• Benjamini-Schramm continuity of root moments of graph polynomials
• The Zeros of the Partial Sums of the Exponential Series
• An asymptotic approximation for the permanent of a doubly stochastic matrix
• An efficient tree decomposition method for permanents and mixed discriminants
• Computing the partition function for graph homomorphisms with multiplicities
• The quantum computer puzzle
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Cited In (12)

• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Computing the permanent of (some) complex matrices
• Spectral independence via stability and applications to Holant-type problems
• On a conjecture of Sokal concerning roots of the independence polynomial
• Angle-restricted sets and zero-free regions for the permanent
• Hafnians, perfect matchings and Gaussian matrices
• Computing permanents of complex diagonally dominant matrices and tensors
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Pfaffians, Hafnians and products of real linear functionals
• A novel approach to perturbative calculations for a large class of interacting boson theories
• On Bobkov's approximate de Finetti representation via approximation of permanents of complex rectangular matrices

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)