Reviews: Inference in Graphical Models via Semidefinite Programming Hierarchies

The authors show how SDP methods based on the Sum-of-Squares (SOS) hierarchy may be used for MAP inference in discrete graphical models, focusing on binary pairwise models. Specifically, an approximate method for binary pairwise models is introduced to solve what is called PSOS(4), then the solution is rounded to an integer solution using a recursive scheme called CLAP (for Confidence Lift And Project). Preliminary empirical results are presented which appear encouraging. This is an interesting direction but I was confused by several aspects. Please could the authors clarify/note the following: 1. l.60-67 Optimizing an LP over a relaxation in the Sherali-Adams hierarchy, and relation to Theorem 1.