BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Complexity of #CSP - David Richerby\, University of Liverpool
DTSTART:20110520T130000Z
DTEND:20110520T140000Z
UID:TALK31175@talks.cam.ac.uk
CONTACT:Bjarki Holm
DESCRIPTION:In the counting constraint satisfaction problem (#CSP)\, we wi
 sh to compute the number of satisfying assignments to a system of relation
 al constraints.  Obviously\, this is at least as hard as determining wheth
 er there is at least one satisfying assignment\, which is already NP-compl
 ete in general as it includes 3-SAT and 3-colourability.\n\nBut if we fix 
 a "constraint language" (a list of specific relations that may be used to 
 define constraints)\, the problem may become easier: for example\, there a
 re constraint languages equivalent to 2-SAT and 2-colourability.  In 2008\
 , Andrei Bulatov showed that\, for any fixed constraint language\, #CSP is
  either computable in polynomial time or is NP-hard (actually\, #P-complet
 e).  However\, his proof is very long and makes deep use of universal alge
 bra\, making it hard to understand for people who are not specialists in t
 hat field.  It was also left open whether the criterion for the dichotomy 
 is decidable.\n\nIn the talk\, I will sketch a new proof of this dichotomy
 \, based just on elementary combinatorics\, and show that the resulting cr
 iterion is decidable in NP.  No knowledge of CSP or universal algebra will
  be assumed.\n\nJoint work with Martin Dyer (University of Leeds). 
LOCATION:Room FW11\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR