Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

Hierarchies of semidefinite relaxations for 0/1 polytopes have been constructed by Lasserre (2001a) and by Lovász and Schrijver (1991). The cut polytope of a graph on n nodes can be expressed as a projection of such a semidefinite relaxation after at most n steps. We show that [n/2] iterations are needed for finding the cut polytope of the complete graph K_n.