Progress on the Complexity of Counting Problems

Jin-Yi Cai (Wisconsin, USA)

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.