14 citations · 37 across the 7 of their papers we have counts for
Showing 2012 · cs.CCShow all
2 papers · 2 filters
cs.CC2012★ 2 cited
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…
cs.CC2012★ 14 cited
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…