Approximating the partition function of the ferromagnetic Potts model

Abstract

We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q>2. Specifically we show that the partition function is hard for the complexity class #RHPi_1 under approximation-preserving reducibility. Thus, it is as hard to approximate the partition function as it is to find approximate solutions to a wide range of counting problems, including that of determining the number of independent sets in a bipartite graph. Our proof exploits the first order phase transition of the "random cluster" model, which is a probability distribution on graphs that is closely related to the q-state Potts model.

Minor corrections

References in corpus (6)

• Approximating the partition function of the ferromagnetic Potts model
• Inapproximability of the Tutte polynomial
• Grassmann Integral Representation for Spanning Hyperforests
• Inapproximability of the Tutte polynomial of a planar graph
• The Complexity of Approximately Counting Stable Matchings
• A Counterexample to rapid mixing of the Ge-Stefankovic Process

Cited by in corpus (28)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Approximating the partition function of the ferromagnetic Potts model
• Algorithmic Pirogov-Sinai theory
• #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
• The expressibility of functions on the Boolean domain, with applications to Counting CSPs
• The Complexity of Approximately Counting Stable Matchings
• FPTAS for #BIS with Degree Bounds on One Side
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• The complexity of approximating conservative counting CSPs
• Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function
• The Complexity of Approximately Counting Tree Homomorphisms
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Functional Clones and Expressibility of Partition Functions
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Approximating the partition function of planar two-state spin systems
• Approximately counting locally-optimal structures
• An Importance Sampling Scheme on Dual Factor Graphs. I. Models in a Strong External Field
• Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
• The Complexity of Approximately Counting Retractions
• Algorithms for the ferromagnetic Potts model on expanders
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
• The Complexity of Computing the Sign of the Tutte Polynomial
• FPRAS for the Potts Model and the Number of $k$-colorings
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
• High Dimensional Discrete Integration over the Hypergrid
• Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs