3 papers
cs.CC2020
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…
cs.CC2020
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…
cs.CC2019
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…