Approximate counting
Speaker:
Andrei Bulatov, Simon Fraser University
Date and Time:
Monday, August 15, 2011 - 11:00am to 12:00pm
Abstract:
While the complexity of exact counting of solutions of CSP is well understood now, approximating the number of solutions is mostly open. In this talk we explain the connections of approximate counting to other areas such as sampling, partition functions, and graph polynomials. We introduce relevant complexity classe and give a short survey of recent results in this area.