  We consider the problem of inference in higher-order undirected graphical
models with binary labels. We formulate this problem as a binary polynomial
optimization problem and propose several linear programming relaxations for it.
We compare the strength of the proposed linear programming relaxations
theoretically. Finally, we demonstrate the effectiveness of these relaxations
by performing a computational study for two important applications, namely,
image restoration and decoding error-correcting codes.
