Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds

Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf

Published Nov 3, 2011• 36 citations
OpenAlex

Abstract

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.

Related papers

Linear vs. semidefinite extended formulations

Samuel Fiorini, Serge Massar, Sebastian Pokutta +2 more

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.

ACM Symposium on Theory of Computing (STOC)•May 19, 2012•190 citations

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Samuel Fiorini, Serge Massar, Sebastian Pokutta +2 more

We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists 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.

Journal of the ACM•May 6, 2015•120 citations

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Samuel Fiorini, Serge Massar, Sebastian Pokutta +2 more

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.

arXiv:1111.0837•Nov 3, 2011•6 citations

Exponential lower bounds on fixed-size psd rank and semidefinite extension complexity

Hamza Fawzi, Pablo A. Parrilo

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.

arXiv:1311.2571•Nov 11, 2013•5 citations

On Polyhedral Approximations of the Positive Semidefinite Cone

Hamza Fawzi

It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n × n positive semidefinite matrices of trace equal to one. We prove two results on the hardness of approximating D with polytopes. We show that if 0 < ε < 1and A is an arbitrary matrix of trace equal to one, any polytope P such that (1-ε) (D-A) ⊂ P ⊂ D-A must have linear programming extension complexity at least [Formula: see text], where c > 0 is a constant that depends on ε. Second, we show that any polytope P such that D ⊂ P and such that the Gaussian width of P is at most twice the Gaussian width of D must have extension complexity at least [Formula: see text]. Our bounds are both superpolynomial in n and demonstrate that there is no generic way of approximating semidefinite programs with compact linear programs. The main ingredient of our proofs is hypercontractivity of the noise operator on the hypercube.

arXiv:1811.09649•Mathematics of Operations Research•Mar 11, 2021•4 citations

The strength of pseudo-expectations : a detailed analysis of the work of Lee, Raghavendra and Steurer on the psd rank of the family of correlation polytopes

Sebastian Gruler

In combinatorial optimization, many problems can be modeled by optimizing a linear functional over a polytope. The standard tool to manage such a problem is the well-known linear programming. But on this occasion, linear programming reaches its limits for example for the family of the correlation polytopes CORRn (n ϵ IN), that forms a very important family of polytopes in combinatorial optimization, because the number of facets of any polytope that maps linearly onto CORRn grows exponentially in n. The question rises whether semidefinite programming, a broad generalization of linear programming, can provide relief. The feasible set of a semidefinite program (SDP) is a so-called spectrahedron, the solution set of a linear matrix inequality (LMI). Instead of the number of facets of the polytope in the case of a linear program, the size of the LMI defining the spectrahedron is a measure for the complexity of the SDP. In their breakthrough work, Lee, Raghavendra and Steurer [LRS] negated 2015 this question. They proved a super-polynomial lower bound in n on the size of any LMI defining any spectrahedron that linearly maps onto CORRn

•Jan 1, 2018•0 citations
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.
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.
It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n × n positive semidefinite matrices of trace equal to one. We prove two results on the hardness of approximating D with polytopes. We show that if 0 < ε < 1and A is an arbitrary matrix of trace equal to one, any polytope P such that (1-ε) (D-A) ⊂ P ⊂ D-A must have linear programming extension complexity at least [Formula: see text], where c > 0 is a constant that depends on ε. Second, we show that any polytope P such that D ⊂ P and such that the Gaussian width of P is at most twice the Gaussian width of D must have extension complexity at least [Formula: see text]. Our bounds are both superpolynomial in n and demonstrate that there is no generic way of approximating semidefinite programs with compact linear programs. The main ingredient of our proofs is hypercontractivity of the noise operator on the hypercube.
In combinatorial optimization, many problems can be modeled by optimizing a linear functional over a polytope. The standard tool to manage such a problem is the well-known linear programming. But on this occasion, linear programming reaches its limits for example for the family of the correlation polytopes CORRn (n ϵ IN), that forms a very important family of polytopes in combinatorial optimization, because the number of facets of any polytope that maps linearly onto CORRn grows exponentially in n. The question rises whether semidefinite programming, a broad generalization of linear programming, can provide relief. The feasible set of a semidefinite program (SDP) is a so-called spectrahedron, the solution set of a linear matrix inequality (LMI). Instead of the number of facets of the polytope in the case of a linear program, the size of the LMI defining the spectrahedron is a measure for the complexity of the SDP. In their breakthrough work, Lee, Raghavendra and Steurer [LRS] negated 2015 this question. They proved a super-polynomial lower bound in n on the size of any LMI defining any spectrahedron that linearly maps onto CORRn