Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Abstract

In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials $\mathcal{C}$ and show that if $p\in \mathcal{C}$ and there is a disk $D$ centered at zero in the complex plane such that $p(G)$ does not vanish on $D$ for all bounded degree graphs $G$, then for each $z$ in the interior of $D$ there exists a deterministic polynomial-time approximation algorithm for evaluating $p(G)$ at $z$. This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated by. Barvinok, which provides a new algorithmic approach besides the existing Markov chain Monte Carlo method and the correlation decay method for these types of problems.

27 pages; some changes have been made based on referee comments. In particular a tiny error in Proposition 4.4 has been fixed. The introduction and concluding remarks have also been rewritten to incorporate the most recent developments. Accepted for publication in SIAM Journal on Computation

References in corpus (11)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Approximating the partition function of the ferromagnetic Potts model
• The computational hardness of counting in two-spin models on d-regular graphs
• Complex zero-free regions at large |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• A Simple FPTAS for Counting Edge Covers
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• On a conjecture of Sokal concerning roots of the independence polynomial
• Computing the partition function for cliques in a graph
• The complexity of approximating complex-valued Ising and Tutte partition functions
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Computing the partition function of a polynomial on the Boolean cube

Cited by in corpus (38)

• Algorithmic Pirogov-Sinai theory
• Fisher zeros and correlation decay in the Ising model
• The Ising Partition Function: Zeros and Deterministic Approximation
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Inapproximability of the independent set polynomial in the complex plane
• Efficient Algorithms for Approximating Quantum Partition Functions
• Weighted counting of solutions to sparse systems of equations
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• Correlation decay and partition function zeros: Algorithms and phase transitions
• On a conjecture of Sokal concerning roots of the independence polynomial
• Algorithmic Cluster Expansions for Quantum Problems
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• More on zeros and approximation of the Ising partition function
• Approximating permanents and hafnians
• Uniqueness of the Gibbs measure for the $4$-state anti-ferromagnetic Potts model on the regular tree
• Lee-Yang Zeros of the antiferromagnetic Ising Model
• Zeros and approximations of Holant polynomials on the complex plane
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Absence of zeros implies strong spatial mixing
• Improved Strong Spatial Mixing for Colorings on Trees
• The limit of the zero locus of the independence polynomial for bounded degree graphs
• Statistical physics approaches to Unique Games
• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• On the location of roots of the independence polynomial of bounded degree graphs
• Glauber dynamics for the hard-core model on bounded-degree $H$-free graphs
• A duality at the heart of Gaussian boson sampling
• Positive bias makes tensor-network contraction tractable
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $\Delta$-regular tree for large $\Delta$
• Efficient sampling and counting algorithms for the Potts model on ${\mathbb{Z}}^d$ at all temperatures
• Counting maximal near perfect matchings in quasirandom and dense graphs
• Rapid Mixing for Colorings via Spectral Independence
• Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits
• Zeros of ferromagnetic 2-spin systems
• Improved bounds for zeros of the chromatic polynomial on bounded degree graphs
• Searching for dense subsets in a graph via the partition function
• Computing the probability of intersection
• Testing systems of real quadratic equations for approximate solutions