14 citations · 37 across the 7 of their papers we have counts for
7 papers
Clifford Gates in the Holant Framework
Jin-Yi Cai, Heng Guo, Tyson Williams
We show that the Clifford gates and stabilizer circuits in the quantum computing literature, which admit efficient classical simulation, are equivalent to affine signatures under a…
A Holant Dichotomy: Is the FKT Algorithm Universal?
Jin-Yi Cai, Zhiguo Fu, Heng Guo +1
We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. This dichotomy is specifically to…
The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems
Jin-Yi Cai, Heng Guo, Tyson Williams
We show that an effective version of Siegel's Theorem on finiteness of integer solutions and an application of elementary Galois theory are key ingredients in a complexity classifi…
Holographic Algorithms Beyond Matchgates
Jin-Yi Cai, Heng Guo, Tyson Williams
Holographic algorithms introduced by Valiant are composed of two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matching…
The Complexity of Planar Boolean #CSP with Complex Weights
Heng Guo, Tyson Williams
We prove a complexity dichotomy theorem for symmetric complex-weighted Boolean #CSP when the constraint graph of the input must be planar. The problems that are #P-hard over genera…
A Complete Dichotomy Rises from the Capture of Vanishing Signatures
Jin-Yi Cai, Heng Guo, Tyson Williams
We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions F on Boolean variables. This extends and unifies…