Output details
11 - Computer Science and Informatics
University of Oxford
Approximating the partition function of the ferromagnetic potts model
<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).