Special Topics on Algorithms: Counting Complexity

Introduction to counting problems and the class #P. Counting problems solvable in polynomial time (Counting perfect matchings in planar graphs, Holographic algorithms). Counting graph homomorphisms, #Constraint Satisfaction Problems, Holant problems. Dichotomy theorems for counting problems. Fully-polynomial approximation schemes (FPTAS, FPRAS) for counting problems. Statistical Physics and the partition function. Descriptive complexity for counting.)