33 citations · 43 across the 3 of their papers we have counts for
3 papers
cs.CC2010★ 3 cited
Non-negative Weighted #CSPs: An Effective Complexity Dichotomy
Jin-Yi Cai, Xi Chen, Pinyan Lu
We prove a complexity dichotomy theorem for all non-negative weighted counting Constraint Satisfaction Problems (CSP). This caps a long series of important results on counting prob…
cs.CC2010★ 7 cited
A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights
Jin-Yi Cai, Xi Chen
The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the p…
cs.CC2010★ 33 cited
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
Jin-Yi Cai, Pinyan Lu, Mingji Xia
Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial…