Weighted counting of solutions to sparse systems of equations

Abstract

Given complex numbers $w_1,\dots ,w_n$, we define the weight $w(X)$ of a set $X$ of 0-1 vectors as the sum of $w_1^{x_1}\cdots w_n^{x_n}$ over all vectors $(x_1,\dots ,x_n)$ in $X$. We present an algorithm, which for a set $X$ defined by a system of homogeneous linear equations with at most $r$ variables per equation and at most $c$ equations per variable, computes $w(X)$ within relative error $\epsilon >0$ in $(rc{)}^{O(\ln n-\ln \epsilon )}$ time provided $|w_j|\le \beta (r\sqrt{c}{)}^{-1}$ for an absolute constant $\beta >0$ and all $j=1,\dots ,n$. A similar algorithm is constructed for computing the weight of a linear code over ${\mathbb{F}}_p$. Applications include counting weighted perfect matchings in hypergraphs, counting weighted graph homomorphisms, computing weight enumerators of linear codes with sparse code generating matrices, and computing the partition functions of the ferromagnetic Potts model at low temperatures and of the hard-core model at high fugacity on biregular bipartite graphs.

The exposition is improved, a couple of inaccuracies corrected

References in corpus (2)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• The Ising Partition Function: Zeros and Deterministic Approximation

Cited by in corpus (6)

• Algorithmic Pirogov-Sinai theory
• Correlation decay and partition function zeros: Algorithms and phase transitions
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature
• Sampling from the low temperature Potts model through a Markov chain on flows
• Zeros and approximations of Holant polynomials on the complex plane
• Computing the probability of intersection