Access Restriction

Author Goldberg, Leslie Ann ♦ Jerrum, Mark
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Approximation algorithms ♦ Potts model ♦ Tutte polynomial ♦ Computation complexity ♦ Phase transition ♦ Random cluster model ♦ Statistical physics
Abstract We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic $\textit{q}-state$ Potts model when $\textit{q}$ > 2. Specifically, we show that the partition function is hard for the complexity class #RHPi 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 $\textit{q}-state$ Potts model.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-11-05
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 59
Issue Number 5
Page Count 31
Starting Page 1
Ending Page 31

Open content in new tab

   Open content in new tab
Source: ACM Digital Library