COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > The ferromagnetic Potts model: phase transition, gadgets and computational complexity

## The ferromagnetic Potts model: phase transition, gadgets and computational complexityAdd to your list(s) Download to your calendar using vCal - Jerrum, M (Queen Mary, London)
- Thursday 21 April 2011, 14:00-15:00
- Seminar Room 2, Newton Institute Gatehouse.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis An instance of the Potts model is defined by a graph of interactions and a number q of different “spins”. A configuration is this model is an assignment of spins to vertices. Each configuration has a weight, which in the ferromagnetic case is greater when more pairs of adjacent spins are alike. The classical Ising model is the special case of q=2 spins. We consider the problem of computing an approximation to the partition function, i.e., weighted sum of configurations, of an instance of the Potts model. Through the random cluster formulation it is possible to make sense of the partition function also for non-integer q. Yet another equivalent formulation is as the Tutte polynomial in the positive quadrant. About twenty years ago, Jerrum and Sinclair gave an efficient (i.e., polynomial-time) algorithm for approximating the partition function of a ferromagnetic Ising system. Attempts to extend this result to q2 have been unsuccessful. At the same time, no convincing evidence has been presented to indicate that such an extension is impossible. In this talk, I sketch a recent result to the effect that, for q>2, approximating the partition function of the ferromagnetic Potts model is hard for a certain complexity class, which contains a large number of other approximation problems for which no efficient approximation algorithm is known. The reduction used to establish this result exploits a first-order phase transition, already known to exist when q>2, to construct a bi-stable combinatorial “gadget”. Along the way, a hypergraph version of the Tutte polynomial arises quite naturally. This is joint work with Leslie Ann Goldberg, University of Liverpool. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 2, Newton Institute Gatehouse
- bld31
Note that ex-directory lists are not shown. |
## Other listsCambridge Next Generation Sequencing Bioinformatics Day Caius-Trinity MedSoc Talks: The Future of Medicine CU Labour Club: All Events## Other talksThrowing light on organocatalysis: new opportunities in enantioselective synthesis Strong Bonds, Affective Labour: Sexually Transmitted Infections and the Work of History Back on the Agenda? Industrial Policy revisited Conference Source-and-Sink Models for Molecular Conduction Why Do We Need Another Biography of Hitler? On being a "barang": Experiences of interviewing fishermen in Cambodia and Indonesia XZ: X-ray spectroscopic redshifts of obscured AGN PTPmesh: Data Center Network Latency Measurements Using PTP A feast of languages: multilingualism in neuro-typical and atypical populations Existence of Lefschetz fibrations on Stein/Weinstein domains Art and Migration CANCELLED: The Loxbridge Triangle: Integrating the East-West Arch into the London Mega-region |