The paper gives a theoretical analysis of Markov random fields. The authors answer the question of when exact inference can be done exactly in a polynomial time. This is a generalization of a result of in Globerson et al. (2015) from grid graphs to general connected graphs, which is on my opinion, a non-trivial generalization. The paper is self contained and readable for the Machine Learning community, although quite technical. Indeed, I consider that it is a theoretical paper that has all the quality for a NeurIPS acceptance. Note however that the technical aspect of the paper leads me to simply recommend a poster, and not a talk.