Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs

DOI10.1137/17M1152966OpenAlexW3161470040WikidataQ115525603 ScholiaQ115525603MaRDI QIDQ4994984

Prasad Raghavendra, Raghu Meka, Pravesh K. Kothari

Publication date: 22 June 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1152966

zbMATH Keywords

communication complexityextended formulationsnonnegative rankrectanglesjuntaslifting theorems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Mixed-integer bilinear programming problems
• Separation of the monotone NC hierarchy
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• The Pattern Matrix Method
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Quantum communication complexity of symmetric predicates
• Integrality gaps for Sherali-Adams relaxations
• Rectangles Are Nonnegative Juntas
• Complexity of Positivstellensatz proofs for the knapsack

This page was built for publication: Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs