Progress on the Complexity of Counting Problems
There has been striking progress recently in the classification
of complexity of Counting Problems. This includes the novel
algorithmic paradigm called Holographic Algorithms pioneered
by Les Valiant; new dichotomy theorems on counting Constraint Satisfaction Problems; dichotomy theorems for Holant Problems;
and Partitions Functions of Graph Homomorphisms with real or complex
values. In this talk we will survey some of this new development.