Hardness of sampling for the anti-ferromagnetic Ising model on random graphs

Neng Huang, Will Perkins, Aaron Potechin

We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree $d$ for large constant $d$, proving that when the normalized invers…