Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
Authors:
Open Access
- 19 June 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 590-603
Abstract
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.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Approximation Limits of Linear Programs (Beyond Hierarchies)Mathematics of Operations Research, 2015
- Exponential Lower Bounds for Polytopes in Combinatorial OptimizationJournal of the ACM, 2015
- The Pattern Matrix MethodSIAM Journal on Computing, 2011
- The Big ExperimentSecEd, 2008
- Quantum communication complexity of symmetric predicatesIzvestiya: Mathematics, 2003
- Complexity of Positivstellensatz proofs for the knapsackcomputational complexity, 2001
- Separation of the Monotone NC HierarchyCombinatorica, 1999
- Cones of Matrices and Set-Functions and 0–1 OptimizationSIAM Journal on Optimization, 1991
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming ProblemsSIAM Journal on Discrete Mathematics, 1990
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication ComplexitySIAM Journal on Computing, 1988