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

DOI10.1145/3055399.3055438zbMath1370.68133arXiv1610.02704OpenAlexW2529974411MaRDI QIDQ4978005

Pravesh K. 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)

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

zbMATH Keywords

lifting theoremsSherali-AdamsLP lower bounds

Mathematics Subject Classification ID

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

Related Items (24)

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

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