Subquadratic Counting via Perfect Marginal Sampling

Xiaoyu Chen, Zongchen Chen, Kuikui Liu +1

We study the computational complexity of approximately computing the partition function of a spin system. Techniques based on standard counting-to-sampling reductions yield $\tilde…