Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
DOI10.1145/2785964zbMath1426.68304arXiv1305.2902MaRDI QIDQ3177756
Daniel Štefanković, Andreas Galanis, Eric Vigoda
Publication date: 2 August 2018
Published in: Journal of the ACM, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.2902
phase transitions; random regular graphs; Potts model; colorings; inapproximability; approximate counting
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
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
05C15: Coloring of graphs and hypergraphs
68W25: Approximation algorithms
82C26: Dynamic and nonequilibrium phase transitions (general) in statistical mechanics
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Uses Software
