Algorithm and Information Colloquium (AIC)

题目：Recent developments in counting complexity　 [全文pdf]

报告人：Mingji Xia（夏盟佶）

时间：2010年1月27日（星期三）下午16:30 – 17:30

地点：软件所5号楼三层报告厅

茶歇：16:00 – 16:30（对面休息室）

摘要：

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.

报告人简介：

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

后续报告预告：

2010年2月3日（星期三）：复杂性理论与密码学（林东岱）