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

DOI10.1145/3055399.3055438zbMATH Open1370.68133arXiv1610.02704OpenAlexW2529974411MaRDI QIDQ4978005FDOQ4978005

Pravesh Kothari, Prasad Raghavendra, Raghu Meka

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{Omega(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, it was only known that linear programs of size $n^{o(logn)}$ cannot beat random guessing for any CSP (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.

Full work available at URL: https://arxiv.org/abs/1610.02704

Recommendations

• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• From weak to strong LP gaps for all CSPs
• From weak to strong linear programming gaps for all constraint satisfaction problems
• Approximating CSPs using LP relaxation

zbMATH Keywords

lifting theoremsSherali-AdamsLP lower bounds

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (24)

• Strong reductions for extended formulations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random oracles and non-uniformity
• Reflections on Proof Complexity and Counting Principles
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Sherali-adams strikes back
• Limitations of semidefinite programs for separable states and entangled games
• Query-to-Communication Lifting for BPP
• On Polyhedral Approximations of the Positive Semidefinite Cone
• A tight approximation algorithm for the cluster vertex deletion problem
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Title not available (Why is that?)
• Title not available (Why is that?)
• No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
• Title not available (Why is that?)
• On differential privacy and adaptive data analysis with bounded space
• On derandomized composition of Boolean functions
• Approximate graph colouring and the hollow shadow
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• On the binary and Boolean rank of regular matrices
• Title not available (Why is that?)
• Lifting Theorems for Equality
• Affine reductions for LPs and SDPs

This page was built for publication: Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978005)