Approximating permanents and hafnians

DOI10.19086/da.1244zbMath1404.15008arXiv1601.07518OpenAlexW2963958955WikidataQ56806482 ScholiaQ56806482MaRDI QIDQ4645007

Alexander I. Barvinok

Publication date: 9 January 2019

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

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

Mathematics Subject Classification ID

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

Related Items

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, A novel approach to perturbative calculations for a large class of interacting boson theories, Angle-Restricted Sets and Zero-Free Regions for the Permanent, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, On a conjecture of Sokal concerning roots of the independence polynomial, Computing permanents of complex diagonally dominant matrices and tensors

Cites Work

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