Andrei Bulatov (SFU)
08/11/13 12:30 Talks
Approximate counting
Speaker:
Andrei Bulatov (Simon Fraser University, Computing Science)
Abstract:
Counting constraint satisfaction problems, in which the goal is to find the number of solutions, rather than to determine if one exists, and their generalization, partition functions, have been in the focus of research over the last several years. While the complexity of exact counting is now well understood, the approximation complexity of this problem remains open. The algebraic structure of such problems plays an important role for the complexity of exact counting. Therefore, the expectation is that the study of approximation complexity will benefit from finding an appropriate algebraic structure, as well. In this talk we survey the challenges we encounter solving this problem, the several approaches that can be taken, and some recent results.
Date:
Friday, November 8, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Andrei Bulatov (Simon Fraser University, Computing Science)
Abstract:
Counting constraint satisfaction problems, in which the goal is to find the number of solutions, rather than to determine if one exists, and their generalization, partition functions, have been in the focus of research over the last several years. While the complexity of exact counting is now well understood, the approximation complexity of this problem remains open. The algebraic structure of such problems plays an important role for the complexity of exact counting. Therefore, the expectation is that the study of approximation complexity will benefit from finding an appropriate algebraic structure, as well. In this talk we survey the challenges we encounter solving this problem, the several approaches that can be taken, and some recent results.
Date:
Friday, November 8, 2013
Time:
12:30 pm - 1:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby