On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy

The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for
constructing a sequence of increasingly tight semidefinite relaxations. It is
known that the hierarchy converges to the 0/1 polytope in n levels and captures
the convex relaxations used in the best available approximation algorithms for
a wide variety of optimization problems.
In this paper we characterize the set of 0/1 integer linear problems and
unconstrained 0/1 polynomial optimization problems that can still have an
integrality gap at level n-1. These problems are the hardest for the Lasserre
hierarchy in this sense.