The Computational Complexity of Holant Problems on 3-Regular Graphs

FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints

(2021) Jin-Yi Cai et al.   THEORY OF COMPUTING SYSTEMS

The Complexity of Boolean Holant Problems with Nonnegative Weights

(2018) Jiabao Lin et al.   SIAM JOURNAL ON COMPUTING

Complexity of Counting CSP with Complex Weights

(2017) Jin-Yi Cai et al.   JOURNAL OF THE ACM

A Complete Dichotomy Rises from the Capture of Vanishing Signatures

(2016) Jin-Yi Cai et al.   SIAM JOURNAL ON COMPUTING

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy

(2016) Jin-Yi Cai et al.   SIAM JOURNAL ON COMPUTING

A Dichotomy for Real Weighted Holant Problems

(2015) Sangxia Huang et al.   COMPUTATIONAL COMPLEXITY

The complexity of complex weighted Boolean #CSP

(2013) Jin-Yi Cai et al.   JOURNAL OF COMPUTER AND SYSTEM SCIENCES

The complexity of the counting constraint satisfaction problem

(2013) Andrei A. Bulatov   JOURNAL OF THE ACM

The Complexity of Symmetric Boolean Parity Holant Problems

(2013) Heng Guo et al.   SIAM JOURNAL ON COMPUTING

An Effective Dichotomy for the Counting Constraint Satisfaction Problem

(2013) Martin Dyer et al.   SIAM JOURNAL ON COMPUTING

Graph Homomorphisms with Complex Values: A Dichotomy Theorem

(2013) Jin-Yi Cai et al.   SIAM JOURNAL ON COMPUTING

The complexity of weighted and unweighted #CSP

(2011) Andrei Bulatov et al.   JOURNAL OF COMPUTER AND SYSTEM SCIENCES

Holographic algorithms by Fibonacci gates

(2011) Jin-Yi Cai et al.   LINEAR ALGEBRA AND ITS APPLICATIONS

Holographic Algorithms

(2008) Leslie G. Valiant   SIAM JOURNAL ON COMPUTING