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:CANCELLED -- The complexity of counting problems -
David Richerby\, University of Essex
DTSTART;TZID=Europe/London:20220218T140000
DTEND;TZID=Europe/London:20220218T150000
UID:TALK169202AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/169202
DESCRIPTION:**TALK CANCELLED DUE TO STORM EUNICE**\n\nEvery co
mputational decision problem ("Is there an X?") ha
s a natural counting variant ("How many X's are th
ere?"). More generally\, computing weighted sums s
uch as integrals\, expectations and partition func
tions in statistical physics can also be seen as c
ounting problems.\n\nI will give an introduction t
o the complexity of solving counting problems. I w
ill focus on variants of constraint satisfaction p
roblems (CSPs) and exactly counting the solutions\
, though I'll also touch on approximate counting.
CSPs are powerful enough to naturally express many
important problems\, but also being restricted en
ough to allow their computational complexity to be
classified completely and elegantly.
LOCATION:FW26
CONTACT:Jamie Vicary
END:VEVENT
END:VCALENDAR