Two counting complexity dichotomy theorems

时间：2011-03-31 分类：学术报告

Title: Two counting complexity dichotomy theorems
Speaker: Mingji Xia
Time: 3:00pm, March 31st (Thursday), 2011.
Venue: Lecture Room, Level 3, Building No. 5, State Key
Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

Abstract: This talk contains two results presented in SODA 2011 and STACS 2011 respectively. The first one resolves the complexity of Boolean domain Holant* problems, and the second one resolves #CSP modulo k problems.Both results reach complexity dichotomy theorems, that is, each problem in the class is either computable in polynomial time, or #P-hard (#_k P hard for #CSP modulo k problems).

Biography:
Mingji Xia is an assistant researcher at State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences.He received the PhD degree from the Institute of Software, Chinese Academy of Sciences in 2008.He is interested in the theoretical computer science in general. His current research topics focus on the complexity of counting problems.