The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs

DOI10.1016/j.ic.2016.07.003zbMath1353.68128arXiv1505.06146OpenAlexW2549123310MaRDI QIDQ342704

Leslie Ann Goldberg, Andreas Galanis

Publication date: 18 November 2016

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

approximate counting2-spin systemsbounded-degree hypergraphscounting constraint satisfaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Zero-freeness and approximation of real Boolean Holant problems, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, The Ising partition function: zeros and deterministic approximation, Approximation via Correlation Decay When Strong Spatial Mixing Fails, Counting hypergraph matchings up to uniqueness threshold, Implementations and the independent set polynomial below the Shearer threshold

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of complex weighted Boolean \#CSP
• Counting in two-spin models on \(d\)-regular graphs
• Structure identification of Boolean relations and plain bases for co-clones
• On the hardness of sampling independent sets beyond the tree threshold
• Complexity of generalized satisfiability counting problems
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• Counting independent sets up to the tree threshold
• On Counting Independent Sets in Sparse Graphs
• Complexity classifications for different equivalence and audit problems for Boolean circuits
• Inapproximability after Uniqueness Phase Transition in Two-Spin Systems
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Counting hypergraph matchings up to uniqueness threshold
• Fast convergence of the Glauber dynamics for sampling independent sets
• FPTAS for Counting Monotone CNF
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The complexity of satisfiability problems
• Mathematical Foundations of Computer Science 2003
• Correlation Decay up to Uniqueness in Spin Systems