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 (4)

• The computational hardness of counting in two-spin models on d-regular graphs
• On a conjecture of Sokal concerning roots of the independence polynomial
• Computing the partition function for cliques in a graph
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots

Cited by in corpus (37)

• 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
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• 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
• Lee-Yang Zeros of the antiferromagnetic Ising Model
• Uniqueness of the Gibbs measure for the $4$-state anti-ferromagnetic Potts model on the regular tree
• Zeros and approximations of Holant polynomials on the complex plane
• Absence of zeros implies strong spatial mixing
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Statistical physics approaches to Unique Games
• The limit of the zero locus of the independence polynomial for bounded degree graphs
• Improved Strong Spatial Mixing for Colorings on Trees
• On zero-free regions for the anti-ferromagnetic Potts model on 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
• On the location of roots of the independence polynomial of bounded degree graphs
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $\Delta$-regular tree for large $\Delta$
• Positive bias makes tensor-network contraction tractable
• 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