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.
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.