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

arXiv: https://arxiv.org/abs/1607.01167 · HTML: https://mlsanity.com/paper/1607.01167/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jul 2016.

## Built on by (most cited first, 1 of 1)

- [Rapid mixing in positively weighted restricted Boltzmann machines](https://mlsanity.com/paper/2604.00963/) (2026)

## Abstract (arXiv)

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∈ cal 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.