Group:Algorithms, Complexity and Cryptography Group
Title: Nonnegatively Weighted #CSP: An Effective Complexity Dichotomy
Speaker: Xi Chen University
Time: 2011-10-28 14:00-2011-10-25 15:30
Venue: FIT 1-222

Abstract:

We prove a complexity dichotomy theorem for all nonnegatively weighted counting Constraint Satisfaction Problems (#CSP). This caps a long series of important results on counting problems including unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the #CSP problem defined by F is solvable in polynomial time; if F does not satisfy the criterion, then the problem is #P-hard. We also show that the question of whether F satisfies the criterion is decidable in NP.

Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of problems, although when specialized to those cases, they are logically equivalent. Our proof mainly uses Linear Algebra, and represents a departure from Universal Algebra, the dominant methodology in recent years.

Joint work with Jin-Yi Cai and Pinyan Lu.



Short Bio:

Xi Chen is an assistant professor in the Computer Science Department of Columbia University. He received his B.S. degree in Physics in 2003 and his Ph.D. in Computer Science in 2007, both from Tsinghua University. His main research interests lie in Algorithmic Game Theory and Theoretical Computer Science in general. He is particularly interested in characterizing the intrinsic difficulties of natural and fundamental problems that arise in the game-theoretic study of Internet and e-commerce.