BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:The complexity of counting problems - David Richer
by\, University of Essex
DTSTART;TZID=Europe/London:20220429T140000
DTEND;TZID=Europe/London:20220429T150000
UID:TALK173453AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/173453
DESCRIPTION:Every computational decision problem ("Is there an
X?") has a natural counting variant ("How many X'
s are there?"). More generally\, computing weighte
d sums such as integrals\, expectations and partit
ion functions in statistical physics can also be s
een as counting problems.\n\nI will give an introd
uction to the complexity of solving counting probl
ems. I will focus on variants of constraint satisf
action problems (CSPs) and exactly counting the so
lutions\, though I'll also touch on approximate co
unting. CSPs are powerful enough to naturally expr
ess many important problems\, but also being restr
icted enough to allow their computational complexi
ty to be classified completely and elegantly.
LOCATION:SS03
CONTACT:Jamie Vicary
END:VEVENT
END:VCALENDAR