BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Evaluating Formulas on Graphs - Anuj Dawar (University of Cambridg
 e)
DTSTART:20101130T130000Z
DTEND:20101130T140000Z
UID:TALK26951@talks.cam.ac.uk
CONTACT:Thomas Tuerk
DESCRIPTION:We consider the computational complexity of the following prob
 lem: given a first-order formula f in the language of graphs (i.e. with on
 e binary relation) and a finite graph G\, determine whether f is satisfied
  in G.  The complexity is generally exponential in the \nsize of f\, thoug
 h polynomial in the size of G. The problem is quite general and encompasse
 s many known hard decision problems on graphs. I well explain how the prob
 lem can be made more tractable on restricted classes of graphs\, which wil
 l lead us to a brief exploration of graph structure theory.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR