Weighted counting of solutions to sparse systems of equations

DOI10.1017/S0963548319000105zbMath1433.68166arXiv1706.05423WikidataQ128045198 ScholiaQ128045198MaRDI QIDQ5222549

Guus Regts, Alexander I. 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

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Hypergraphs (05C65) Linear codes (general theory) (94B05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) 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) Approximation algorithms (68W25)

Related Items

The complexity of approximating the complex-valued Potts model, Zeros and approximations of holant polynomials on the complex plane, Algorithmic Pirogov-Sinai theory, Fast mixing via polymers for random graphs with unbounded degree, Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures, Sampling from the low temperature Potts model through a Markov chain on flows, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Approximation Algorithms for the Random Field Ising Model, Algorithms for #BIS-Hard Problems on Expander Graphs, Computing permanents of complex diagonally dominant matrices and tensors, The complexity of approximating the complex-valued Potts model, The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs, Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Combinatorics and complexity of partition functions
• The complexity of computing the permanent
• Benjamini-Schramm continuity of root moments of graph polynomials
• NP is as easy as detecting unique solutions
• Percolation and the hard-core lattice gas model
• The Ising partition function: zeros and deterministic approximation
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Computing permanents of complex diagonally dominant matrices and tensors
• Improved bounds for sampling colorings
• The hardness of decoding linear codes with preprocessing
• Information, Physics, and Computation
• On the inherent intractability of certain coding problems (Corresp.)
• Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
• Computing the Partition Function of a Polynomial on the Boolean Cube
• Left and right convergence of graphs with bounded degree
• Algorithmic Pirogov-Sinai theory
• Improved Bounds for Randomly Sampling Colorings via Linear Programming
• Algorithms for #BIS-hard problems on expander graphs
• Statistical Mechanics of Lattice Systems