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

DOI10.1145/3055399.3055438MaRDI QIDQ4978005zbMATH OpenOpenAlexFDO

Authors Pravesh Kothari, Raghu Meka, Prasad Raghavendra

Publication date 17 August 2017

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

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

zbMATH Keywords

lifting theoremsLP lower boundsSherali-Adams

Mathematics Subject Classification ID

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

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.

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

Cited in

(27)

• Random oracles and non-uniformity
• Affine reductions for LPs and SDPs
• Limitations of semidefinite programs for separable states and entangled games
• On derandomized composition of Boolean functions
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• On the binary and Boolean rank of regular matrices
• From weak to strong linear programming gaps for all constraint satisfaction problems
• On the complexity of random satisfiability problems with planted solutions
• Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
• Sunflowers and quasi-sunflowers from randomness extractors
• On polyhedral approximations of the positive semidefinite cone
• Reflections on Proof Complexity and Counting Principles
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Lifting Theorems for Equality
• Sherali-adams strikes back
• From weak to strong LP gaps for all CSPs
• Query-to-communication lifting for BPP
• scientific article; zbMATH DE number 7250155 (Why is no real title available?)
• Sherali-Adams strikes back
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Subsampling mathematical relaxations and average-case complexity
• A tight approximation algorithm for the cluster vertex deletion problem
• On differential privacy and adaptive data analysis with bounded space
• Sum-of-squares lower bounds for densest k-subgraph
• Approximate graph colouring and the hollow shadow
• Towards PNP from extended Frege lower bounds

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)