Computation of the Lasserre Ranks of Some Polytopes

Over the years, various lift-and-project methods have been proposed to construct hierarchies of successive linear or semidefinite relaxations of a 0–1 polytope P ⫅ ℝⁿ that converge to P in n steps. Many such methods have been shown to require n steps in the worst case. In this paper, we show that the method of Lasserre also requires n steps in the worst case.