Weighted counting of solutions to sparse systems of equations

DOI10.1017/S0963548319000105zbMATH Open1433.68166arXiv1706.05423WikidataQ128045198 ScholiaQ128045198MaRDI QIDQ5222549FDOQ5222549

Authors: Guus Regts, Alexander Barvinok 

Publication date: 6 April 2020

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

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.

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

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

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)

Cites Work

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

Cited In (16)

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

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)