Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results

DOI10.4230/LIPIcs.APPROX-RANDOM.2014.677zbMath1359.68131arXiv1311.4839OpenAlexW2565279154MaRDI QIDQ2969655

Daniel Štefanković, Andreas Galanis, Linji Yang, Eric Vigoda

Publication date: 22 March 2017

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

zbMATH Keywords

phase transitionrandom regular graphsspin systemsapproximate countingferromagnetic Potts model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Phase transitions (general) in equilibrium statistical mechanics (82B26) 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

Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials ⋮ Counting Constraint Satisfaction Problems. ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs