Approximating the Partition Function of the Ferromagnetic Potts Model

DOI10.1007/978-3-642-14165-2_34zbMath1288.68091arXiv1002.0986OpenAlexW2570395877MaRDI QIDQ3587394

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 7 September 2010

Published in: Journal of the ACM, Automata, Languages and Programming (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionstatistical physicsPotts modelTutte polynomialapproximation algorithmsrandom cluster modelcomputation complexity

Mathematics Subject Classification ID

Graph polynomials (05C31) Graph theory (including graph drawing) in computer science (68R10) 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) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region, The complexity of approximating the complex-valued Potts model, Approximately counting locally-optimal structures, Approximately Counting Locally-Optimal Structures, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, Random cluster dynamics for the Ising model is rapidly mixing, Mixing of the Glauber dynamics for the ferromagnetic Potts model, An FPTAS for the hardcore model on random regular bipartite graphs, Algorithmic Pirogov-Sinai theory, The Complexity of Approximately Counting Tree Homomorphisms, Fast mixing via polymers for random graphs with unbounded degree, Approximately counting independent sets in bipartite graphs via graph containers, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Complexity classification of the six-vertex model, Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019, The complexity of approximately counting stable matchings, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Counting Constraint Satisfaction Problems., Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, Algorithms for #BIS-Hard Problems on Expander Graphs, Faster exponential-time algorithms for approximately counting independent sets, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Unnamed Item, Zero-free regions of partition functions with applications to algorithms and graph limits, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid, The complexity of approximating conservative counting CSPs, Approximating the partition function of planar two-state spin systems, Approximate Counting via Correlation Decay in Spin Systems, The complexity of approximating the complex-valued Potts model, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Unnamed Item, Functional clones and expressibility of partition functions