![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
David Richerby, University of Essex
Friday 18 February 2022, 14:00-15:00
CANCELLED -- The complexity of counting problems
- đ¤ Speaker: David Richerby, University of Essex
- đ Date & Time: Friday 18 February 2022, 14:00 - 15:00
- đ Venue: FW26
Abstract
TALK CANCELLED DUE TO STORM EUNICE
Every computational decision problem (“Is there an X?”) has a natural counting variant (“How many X’s are there?”). More generally, computing weighted sums such as integrals, expectations and partition functions in statistical physics can also be seen as counting problems.
I will give an introduction to the complexity of solving counting problems. I will focus on variants of constraint satisfaction problems (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 enough to allow their computational complexity to be classified completely and elegantly.
Series This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.
Included in Lists
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Computing and Mathematics
- Department of Computer Science and Technology talks and seminars
- FW26
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Martin's interesting talks
- School of Technology
- tcw57âs list
- Trust & Technology Initiative - interesting events
- yk373's list
- yk449
Note: Ex-directory lists are not shown.