In Rothvo it was shown that there exists a 0 1 polytope (a polytope whose vertices are in 0,1 ^ n ) such that any higher-dimensional polytope projecting to it must have 2^ (n) facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0 1 polytope with high PSD extension complexity was left open. We answer this question in the affirmative by showing that there is a 0 1 polytope such that any spectrahedron projecting to it must be the intersection of a semidefinite cone of dimension 2^ (n) and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.
The basis for the study of linear and semidefinite extended formulations is the work of Yannakakis (see @cite_11 and @cite_15 ). The existence of a 0 1 polytope with exponential extension complexity was shown in @cite_13 which in turn was inspired by @cite_9 . The first explicit example, answering a long standing open problem of Yannakakis, was provided in @cite_7 which, together with @cite_2 , also lay the foundation for the study of extended formulations over general closed convex cones. In @cite_7 it was also shown that there exist matrices with large nonnegative rank but small semidefinite rank, indicating that semidefinite extended formulations can be exponentially stronger than linear ones, however falling short of giving an explicit proof. They thereby separated the expressive power of linear programs from those of semidefinite programs and raised the question:
@cite_7 @cite_9 @cite_2 @cite_15 @cite_13 @cite_11
2119368733 2068422506 2138677859 2952253187 87237596
We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. THE theory of switching circuits may be divided into two major divisions, analysis and synthesis. The problem of analysis, determining the manner of operation of a given switching circuit, is comparatively simple. The inverse problem of finding a circuit satisfying certain given operating conditions, and in particular the best circuit is, in general, more difficult and more important from the practical standpoint. A basic part of the general synthesis problem is the design of a two-terminal network with given operating characteristics, and we shall consider some aspects of this problem. In this paper, we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone. Such a representation or lift of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over its affine slices. We show that the existence of a lift of a convex set to a cone is equivalent to the existence of a factorization of an operator associated to the set and its polar via elements in the cone and its dual. This generalizes a theorem of Yannakakis that established a connection between polyhedral lifts of a polytope and nonnegative factorizations of its slack matrix. Symmetric lifts of convex sets can also be characterized similarly. When the cones live in a family, our results lead to the definition of the rank of a convex set with respect to this family. We present results about this rank in the context of cones of positive semidefinite matrices. Our methods provide new tools for understanding cone lifts of convex sets. We prove that there are 0 1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a sets X 0,1 ^n such that conv(X) must have extension complexity at least 2^ n 2 * (1-o(1)) . In other words, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on NP not contained in P_ poly , our result rules out the existence of any compact formulation for the TSP polytope, even if the formulation may contain arbitrary real numbers.