Approximating permanents and hafnians
From MaRDI portal
Publication:4645007
DOI10.19086/da.1244zbMath1404.15008arXiv1601.07518OpenAlexW2963958955WikidataQ56806482 ScholiaQ56806482MaRDI QIDQ4645007
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
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
