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

DOI10.1016/j.ic.2016.07.003zbMath1353.68128arXiv1505.06146MaRDI 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 counting; 2-spin systems; bounded-degree hypergraphs; counting constraint satisfaction

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

82C20: Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics

82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)