题目：Complexity Dichotomies of Counting Problems 报告人：Pinyan Lu (陆品燕)
Theory Group, Microsoft Research Asia 时间：2010年12月07日（星期二）14:00 –15:00 地点：蒙民伟楼311室 摘要:
We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (#CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and #CSP can be viewed as special cases of Holant Problems. Because the framework is more stringent, previous dichotomy theorems for #CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the #CSP framework. A number of complexity dichotomy theorems in this framework were proved, and I will introduce some of them in this talk.  报告人简介:
Pinyan Lu(陆品燕) is a researcher at Theory Group of Microsoft Research Asia. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). He is mainly interested in complexity theory, algorithms design and algorithmic game theory.
|
