Before revision: We provide the first polynomial-sample and polynomial-time algorithm for learning tree-structured Ising models. In particular, we show that n-variable tree-structured Ising models can be learned computationally-efficiently to within total variation distance ~ \epsilon from an optimal O(n \log n/\epsilon^2) samples, where O( . ) hides an absolute constant which  does not depend on the model being learned -- neither its tree nor the magnitude of its edge strengths, on which we place no assumptions.
After revision: We show that n-variable tree-structured Ising models can be learned computationally-efficiently to within total variation distance ~ \epsilon from an optimal O(n \log n/\epsilon^2) samples, where O( . ) hides an absolute constant which does not depend on the model being learned -- neither its tree nor the magnitude of its edge strengths, on which we place no assumptions.