Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

Pravesh Kumar Kothari, Raghu Meka, Prasad Raghavendra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages590-603
Number of pages14
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F128415
ISSN (Print)0737-8017

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
CountryCanada
CityMontreal
Period6/19/176/23/17

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs'. Together they form a unique fingerprint.

  • Cite this

    Kothari, P. K., Meka, R., & Raghavendra, P. (2017). Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In P. McKenzie, V. King, & H. Hatami (Eds.), STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (pp. 590-603). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415). Association for Computing Machinery. https://doi.org/10.1145/3055399.3055438