Computing the permanent of (some) complex matrices

DOI10.1007/s10208-014-9243-7zbMath1347.65082arXiv1405.1303OpenAlexW1997999115MaRDI QIDQ285430

Alexander I. Barvinok

Publication date: 19 May 2016

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmpermanenthafnian

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40) Complexity and performance of numerical algorithms (65Y20)

Related Items

Zero-freeness and approximation of real Boolean Holant problems, Zeros and approximations of holant polynomials on the complex plane, Grassmann geometry of zero sets in reproducing kernel Hilbert spaces, Algorithmic Pirogov-Sinai theory, Correlation decay and the absence of zeros property of partition functions, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Computing the Partition Function of a Polynomial on the Boolean Cube, Nonnegative tensors revisited: plane stochastic tensors, The Ising partition function: zeros and deterministic approximation, Algorithms for #BIS-Hard Problems on Expander Graphs, Approximating permanents and hafnians, Computing the partition function for graph homomorphisms, Acyclic polynomials of graphs, The permanent functions of tensors, Unnamed Item, Unnamed Item, On a conjecture of Sokal concerning roots of the independence polynomial, Fisher zeros and correlation decay in the Ising model, Fisher Zeros and Correlation Decay in the Ising Model, On the classical complexity of sampling from quantum interference of indistinguishable bosons, Computing permanents of complex diagonally dominant matrices and tensors, New permanent approximation inequalities via identities, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Gauges, loops, and polynomials for partition functions of graphical models, A Tight Analysis of Bethe Approximation for Permanent

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Computing the partition function for graph homomorphisms
• A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• 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
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Two Algorithmic Results for the Traveling Salesman Problem
• Mathematical Foundations of Computer Science 2005
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• The Euclidean distance degree of an algebraic variety