Approximation via Correlation Decay When Strong Spatial Mixing Fails
Approximation via Correlation Decay When Strong Spatial Mixing Fails
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 the partition function of antiferromagnetic 2-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means …