37 citations · 171 across the 30 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 2 cited
Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
Heng Guo, Pinyan Lu
We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes. The threshold we obtain is almo…
cs.CC2015
Approximation via Correlation Decay when Strong Spatial Mixing Fails
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg +2
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of…
cs.CC2015★ 11 cited
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…