Title：Recent developments in counting complexity　 [全文pdf]

Speaker：Mingji Xia（夏盟佶）

Time：16:30 – 17:30,Jan.27,2010

Venue：Lecture Room, State Key Lab of Computer Science, Level 3 Building #5

Abstract：

In the past several years, there are quite a few complexity dichotomy theorems for counting problems classes of #CSP, counting graph homomorphisms, and Holant problems. We introduce three of them and compare them in a general counting problem notation #F|G.

We also introduce one important method in this area, Valiant's holographic reduction, and how it stimulates the study of Holant problems.

Biography：

Mingji Xia received his ph D in the Institute of Software, Chinese Academy of Sciences in 2008.