BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The ferromagnetic Potts model:  phase transition\, gadgets and com
 putational complexity - Jerrum\, M (Queen Mary\, London)
DTSTART:20110421T130000Z
DTEND:20110421T140000Z
UID:TALK30895@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:An instance of the Potts model is defined by a graph of intera
 ctions and a number q \nof  different "spins".  A configuration is this mo
 del is an assignment of spins to vertices.\nEach configuration has a weigh
 t\, which in the ferromagnetic case is greater when more\npairs of adjacen
 t spins are alike.  The classical Ising model is the special case of q=2\n
 spins.  We consider the problem of computing an approximation to the parti
 tion function\,\ni.e.\, weighted sum of configurations\, of an instance of
  the Potts model.\nThrough the random cluster formulation it is possible t
 o make sense\nof the partition function also for non-integer q.  Yet anoth
 er equivalent formulation \nis as the Tutte polynomial in the positive qua
 drant.\n\nAbout twenty years ago\, Jerrum and Sinclair gave an efficient (
 i.e.\, polynomial-time)\nalgorithm for approximating the partition functio
 n of a ferromagnetic Ising system.\nAttempts to extend this result to q2 h
 ave been unsuccessful.\nAt the same time\, no convincing evidence has been
  presented to indicate that\nsuch an extension is impossible.  In this tal
 k\, I sketch a recent result to the effect that\, \nfor q>2\, approximatin
 g the partition function of the ferromagnetic Potts model is hard \nfor a 
 certain complexity class\, which contains a large number of other approxim
 ation\nproblems for which no efficient approximation algorithm is known.  
 \nThe reduction used to establish this result \nexploits a first-order pha
 se transition\, already known to exist when q>2\,\nto construct a bi-stabl
 e combinatorial "gadget".  Along the way\, a hypergraph\nversion of the Tu
 tte polynomial arises quite naturally.\n\nThis is joint work with Leslie A
 nn Goldberg\, University of Liverpool. \n
LOCATION:Seminar Room 2\, Newton Institute Gatehouse
END:VEVENT
END:VCALENDAR