BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Parameterised Proof Complexity - Dantchev\, S (Durham University)
DTSTART:20120326T130000Z
DTEND:20120326T140000Z
UID:TALK37095@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:I will start by introducing the basic notion of a parameterise
 d proof as defined by B. Martin\, S. Szeider and myself back in 2007\, and
  will discuss a complexity gap theorem theorem for generic parameterisatio
 n of tree-like resolution. I will then move onto results that have been ob
 tained since them by various researchers\, including parameterised lower b
 ounds for the pigeon-hole principle in resolution and for the maximum cliq
 ue in random graphs in tree-like resolution. I will conclude with some new
  results due to B. Martin and myself on\nparameterised proofs for W[1] as 
 well as with some open problems.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR