  With the goal of obtaining strong relaxations for binary polynomial
optimization problems, we introduce the pseudo-Boolean polytope defined as the
convex hull of the set of binary points satisfying a collection of equations
containing pseudo-Boolean functions. By representing the pseudo-Boolean
polytope via a signed hypergraph, we obtain sufficient conditions under which
this polytope has a polynomial-size extended formulation. Our new framework
unifies and extends all prior results on the existence of polynomial-size
extended formulations for the convex hull of the feasible region of binary
polynomial optimization problems of degree at least three.
