  There has been a lot of interest recently in proving lower bounds on the size
of linear programs needed to represent a given polytope P. In a breakthrough
paper Fiorini et al. [Proceedings of 44th ACM Symposium on Theory of Computing
2012, pages 95-106] showed that any linear programming formulation of
maximum-cut must have exponential size. A natural question to ask is whether
one can prove such strong lower bounds for semidefinite programming
formulations. In this paper we take a step towards this goal and we prove
strong lower bounds for a certain class of SDP formulations, namely SDPs over
the Cartesian product of fixed-size positive semidefinite cones. In practice
this corresponds to semidefinite programs with a block-diagonal structure and
where blocks have constant size d. We show that any such extended formulation
of the cut polytope must have exponential size (when d is fixed). The result of
Fiorini et al. for LP formulations is obtained as a special case when d=1. For
blocks of size d=2 the result rules out any small formulations using
second-order cone programming. Our study of SDP lifts over Cartesian product of
fixed-size positive semidefinite cones is motivated mainly from practical
considerations where it is well known that such SDPs can be solved more
efficiently than general SDPs. The proof of our lower bound relies on new
results about the sparsity pattern of certain matrices with small psd rank,
combined with an induction argument inspired from the recent paper by Kaibel
and Weltge [arXiv:1307.3543] on the LP extension complexity of the correlation
polytope.
