BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:The ferromagnetic Potts model: phase transition\,
gadgets and computational complexity - Jerrum\, M
(Queen Mary\, London)
DTSTART;TZID=Europe/London:20110421T140000
DTEND;TZID=Europe/London:20110421T150000
UID:TALK30895AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/30895
DESCRIPTION:An instance of the Potts model is defined by a gra
ph of interactions and a number q \nof different
"spins". A configuration is this model is an assi
gnment of spins to vertices.\nEach configuration h
as a weight\, which in the ferromagnetic case is g
reater when more\npairs of adjacent spins are alik
e. The classical Ising model is the special case
of q=2\nspins. We consider the problem of computi
ng an approximation to the partition function\,\ni
.e.\, weighted sum of configurations\, of an insta
nce of the Potts model.\nThrough the random cluste
r formulation it is possible to make sense\nof the
partition function also for non-integer q. Yet a
nother equivalent formulation \nis as the Tutte po
lynomial in the positive quadrant.\n\nAbout twenty
years ago\, Jerrum and Sinclair gave an efficient
(i.e.\, polynomial-time)\nalgorithm for approxima
ting the partition function of a ferromagnetic Isi
ng system.\nAttempts to extend this result to q2 h
ave been unsuccessful.\nAt the same time\, no conv
incing evidence has been presented to indicate tha
t\nsuch an extension is impossible. In this talk\
, I sketch a recent result to the effect that\, \n
for q>2\, approximating the partition function of
the ferromagnetic Potts model is hard \nfor a cert
ain complexity class\, which contains a large numb
er of other approximation\nproblems for which no e
fficient approximation algorithm is known. \nThe
reduction used to establish this result \nexploits
a first-order phase transition\, already known to
exist when q>2\,\nto construct a bi-stable combin
atorial "gadget". Along the way\, a hypergraph\nv
ersion of the Tutte polynomial arises quite natura
lly.\n\nThis is joint work with Leslie Ann Goldber
g\, University of Liverpool. \n
LOCATION:Seminar Room 2\, Newton Institute Gatehouse
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR