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.
In a parallel line of work, Chan, Lee, Raghavendra and Steurer @cite_25 proved lower bounds on the size of linear programs for constraint satisfaction problems by relating it to known Sherali-Adams integrality gaps using techniques from Fourier analysis and convex optimization. For instance, they proved that any polynomial sized LP for Max-Cut on @math -node graphs cannot beat the trivial approximation factor of @math . Recently, Kothari, Meka and Raghavendra @cite_19 improved their lower bounds to @math for some constant @math . Lee, Raghavendra and Steurer @cite_2 proved that similar situation arises for SDP relaxations: when it comes to maximum constraint satisfaction problems, SDPs of size polynomial size cannot perform much better than sums of squares relaxations of constant degree. For instance, this implies that for @math - @math - @math , no SDP of polynomial size can beat the trivial approximation factor of @math .
@cite_19 @cite_25 @cite_2
2529974411 2038907843 2006830086
We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as nΩ(1)-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results; previously, the best known lower bounds were quasi-polynomial in n (Chan, Lee, Raghavendra, Steurer 2013). Our bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The main ingredient in our results is a new structural result on "high-entropy rectangles" that may of independent interest in communication complexity. We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1 2 and any such linear program for Max 3-Sat has an integrality gap of 7 8. We investigate the optimality of (1+ )-approximation algorithms obtained via the dimensionality reduction method. We show that: --Any data structure for the (1+ )-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use n^ ( 1 ^2 ) space. --Any algorithm for the (1+ )-approximate closest substring problem must run in time exponential in 1 ^ 2 - for any > 0 (unless 3SAT can be solved in subexponential time) Both lower bounds are (essentially) tight.