37 citations · 171 across the 30 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
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★ 4 cited
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems
Jin-Yi Cai, Xi Chen, Heng Guo +1
A two-state spin system is specified by a 2 x 2 matrix A = {A_{0,0} A_{0,1}, A_{1,0} A_{1,1}} = {β1, 1 γ} where β, γ\ge 0. Given an input graph G=(V,E), the partition function Z_A(…
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…