There has been significant progress in the Complexity Theory of counting problems.  These advances are made in at least three frameworks for such problems: Graph Homomorphisms (GH), Constraint Satisfaction Problems (CSP), and Holant Problems. It is also closely related to the theory of Holographic Algorithms and Reductions. One major aim in this research is to prove broad classification theorems called dichotomy theorems. These theorems classify every problem in a broad class into either solvable in polynomial time or #P-hard.

We will start with some introductions to the three frameworks. The aim is to get us familiarize with the basic concepts and techniques in a relatively simple setting. The exact theorems proved will be of secondary importance at this point.

Then we consider Graph Homomorphism, which was defined by Lovasz in 1967. Our first main aim of the course is to present the full proof (over 100 pages) of the recent dichotomy theorem for complex-valued GH partition functions.  A second main topic is to present the recent dichotomy theorems for counting CSP.  The third main topic is to discuss Holographic Algorithms.  We also intend to discuss connections with statistical physics (Hardcore/Independent Sets, the Ising model, the Potts model, the Tutte polynomial, etc.)