We consider the problem of learning the structure of Ising models (pairwise
binary Markov random fields) from i.i.d. samples. While several methods have
been proposed to accomplish this task, their relative merits and limitations
remain somewhat obscure. By analyzing a number of concrete examples, we show
that low-complexity algorithms often fail when the Markov random field develops
long-range correlations. More precisely, this phenomenon appears to be related
to the Ising model phase transition (although it does not coincide with it).