Weighted counting of solutions to sparse systems of equations

DOI10.1017/S0963548319000105MaRDI QIDQ5222549zbMATH OpenWikidataFDO

Authors Guus Regts, Alexander Barvinok

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Computational aspects related to convexity (52B55) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Linear codes (general theory) (94B05)

Abstract: Given complex numbers $w_1,ldots,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,ldots,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(lnn-lnepsilon)}$ time provided $$ for an absolute constant $$ and all $j=1,ldots,n$. A similar algorithm is constructed for computing the weight of a linear code over ${BbbF}_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.

Recommendations

• Computing the partition function for perfect matchings in a hypergraph
• Some algorithmic applications of partition functions in combinatorics
• Scientific article; zbMATH DE number 2119675
• Complexity of counting CSP with complex weights
• Solving linear equations parameterized by Hamming weight

Cites work

• scientific article; zbMATH DE number 54272 (Why is no real title available?)
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Algorithmic Pirogov-Sinai theory
• Algorithms for #BIS-hard problems on expander graphs
• Benjamini-Schramm continuity of root moments of graph polynomials
• Combinatorics and complexity of partition functions
• Computing permanents of complex diagonally dominant matrices and tensors
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Computing the partition function of a polynomial on the Boolean cube
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Improved bounds for randomly sampling colorings via linear programming
• Improved bounds for sampling colorings
• Information, Physics, and Computation
• Left and right convergence of graphs with bounded degree
• NP is as easy as detecting unique solutions
• On the inherent intractability of certain coding problems (Corresp.)
• Percolation and the hard-core lattice gas model
• Statistical mechanics of lattice systems. A concrete mathematical introduction
• The Ising partition function: zeros and deterministic approximation
• The complexity of computing the permanent
• The hardness of decoding linear codes with preprocessing
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Cited in

(16)

• Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
• The complexity of approximating the complex-valued Potts model
• Computing permanents of complex diagonally dominant matrices and tensors
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
• The complexity of approximating the complex-valued Potts model
• A structured view on weighted counting with relations to counting, quantum computation and applications
• Approximation Algorithms for the Random Field Ising Model
• Algorithmic Pirogov-Sinai theory
• Algorithms for \#BIS-hard problems on expander graphs
• scientific article; zbMATH DE number 4049714 (Why is no real title available?)
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• Fast mixing via polymers for random graphs with unbounded degree
• Sampling from the low temperature Potts model through a Markov chain on flows
• Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures
• Smoothed counting of 0–1 points in polyhedra
• Zeros and approximations of holant polynomials on the complex plane

This page was built for publication: Weighted counting of solutions to sparse systems of equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222549)