12 citations · 20 across the 3 of their papers we have counts for
4 papers · 1 filter
A Dichotomy for Real Boolean Holant Problems
Shuai Shao, Jin-Yi Cai
We prove a complexity dichotomy for Holant problems on the boolean domain with arbitrary sets of real-valued constraint functions. These constraint functions need not be symmetric…
From Holant to Quantum Entanglement and Back
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
Holant problems are intimately connected with quantum theory as tensor networks. We first use techniques from Holant theory to derive new and improved results for quantum entanglem…
Beyond #CSP: A Dichotomy for Counting Weighted Eulerian Orientations with ARS
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
We define and explore a notion of unique prime factorization for constraint functions, and use this as a new tool to prove a complexity classification for counting weighted Euleria…
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
We discover new P-time computable six-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. We further prove that there are no more: To…