We give a polynomial time algorithm for learning $O(log n)$-juntas over smoothed Markov Random fields