BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T013825Z
UID:Seminar-dept-427@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20161129T130000
DTEND:20161129T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Leslie Ann Goldberg: Graph algorithms and the complexity of counting\n\nThe field of "computational counting" considers counting problems such as "how many proper  3-colourings does an input graph have"? It is well-known that this particular problem is #P-hard to solve\n\nexactly, and it is also clear that it is at least NP-hard to solve approximately (since it is NP-hard to tell whether the answer is zero). Since approximate counting arises in many applications (such as computing\n\nprobabilities and partition functions) there is a lot of research aimed at classifying counting problems, to see which ones can be solved approximately. This talk will contain a survey/background of the area, but\n\nI will also tell you about a recent result, which is joint work with Andreas Galanis and Mark Jerrum, which completely classifies a family of (approximate) counting problems.  The problems involve counting homomorphisms to a fixed graph~$H$ (I'll tell you what that means in the talk!) and it turns out that work on hereditary graph classes makes it possible to completely determine, for a given~$H$, the complexity of the corresponding counting problem.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=427
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR