We prove that any extended formulation that approximates the matching polytope on @math -vertex graphs up to a factor of @math for any @math must have at least @math defining inequalities where @math is an absolute constant. This is tight as exhibited by the @math approximating linear program obtained by dropping the odd set constraints of size larger than @math from the description of the matching polytope. Previously, a tight lower bound of @math was only known for @math [Rothvoss, STOC '14; Braun and Pokutta, IEEE Trans. Information Theory '15] whereas for @math , the best lower bound was @math [Rothvoss, STOC '14]. The key new ingredient in our proof is a close connection to the non-negative rank of a lopsided version of the unique disjointness matrix.
When it comes to approximations, the problems discussed above have exponential size LP lower bounds. The matching problem is very different in the sense that for any @math , it has an LP of size @math which achieves a @math approximation. We show that for the matching problem this is best possible. A similar situation arises for the Max-Knapsack problem for which Bienstock @cite_9 gave an LP of size @math which achieves a @math approximation for any @math . An exponential lower bound for exact extended formulations for Max-Knapsack follows by a reduction from the unique disjointness matrix @cite_3 @cite_22 (also see @cite_23 which proves a better lower bound by using a different construction). It is unclear how to extend the aforementioned reduction from unique disjointness to prove a strong lower bound for any @math approximation for Max-Knapsack. A lower bound even in the case of @math approximation remains an interesting open problem.
@cite_9 @cite_23 @cite_22 @cite_3
2065139435 2788289283 2031923588
We show that for each 0<@e@?1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables, whose value is at most (1+@e) times the value of the integer program. We exhibit an @math -node graph whose independent set polytope requires extended formulations of size exponential in @math . Previously, no explicit examples of @math -dimensional @math -polytopes were known with extension complexity larger than exponential in @math . Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth. We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than 2nδ, for some constant δ > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7 8-approximation for max-sat.