Output details
11 - Computer Science and Informatics
University of Oxford
Article title
Approximating the partition function of the ferromagnetic potts model
Type
D - Journal article
Title of journal
Journal of the ACM
Article number
25
Volume number
59
Issue number
5
First page of article
1
ISSN of journal
0004-5411
Year of publication
2012
Number of additional authors
1
Additional information
<10>
A preliminary version won the best-paper prize at the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) Track A (Algorithms, Automata, Complexity and Games). Prior to this paper, it was known how to exploit phase transitions in statistical physics to show that particular Markov Chain Monte Carlo algorithms fail. This paper showed much more – that phase transitions can be used to give complexity-theoretic lower bounds (showing that every algorithm fails, subject to complexity-theoretic assumptions). Sly similarly used phase transitions to show hardness for the hardcore model a few months later (at FOCS 2010).
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
