@inproceedings{63bcba4777a44d16acafefe76b956318,
title = "Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs",
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 = "LP lower bounds, Lifting theorems, Sherali-Adams",
author = "Kothari, {Pravesh K.} and Raghu Meka and Prasad Raghavendra",
note = "Publisher Copyright: {\textcopyright} 2017 ACM.; 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 ; Conference date: 19-06-2017 Through 23-06-2017",
year = "2017",
month = jun,
day = "19",
doi = "10.1145/3055399.3055438",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "590--603",
editor = "Pierre McKenzie and Valerie King and Hamed Hatami",
booktitle = "STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing",
}