Abstract

Constraint Satisfaction Problems (CSPs) have been studied extensively in the literature, and their counting version provides a sufficiently broad framework to address a large class of counting problems for which one can hope to prove complexity dichotomy theorems. In this talk we will review the recent sequence of dichotomy theorems on counting CSP and showcase some of the techniques developed in these works.

Complexity of generalized satisfiability counting problems, Creignou and Hermann
The complexity of the counting constraint satisfaction problem, Bulatov
An effective dichotomy for the counting constraint satisfaction problem, Dyer and Richerby
The complexity of weighted and unweighted #CSP, Bulatov, Dyer, Goldberg, Jalsenius, Jerrum and Richerby
Non-negative weighted #CSPs: An effective complexity dichotomy, Cai, Chen and Lu
Complexity of counting CSP with complex weights, Cai and Chen
 

The first session of this mini course will take place on Tuesday, January 26 from 11:00 am – 12:00 pm. 

Attachment

Video Recording