# Approximate Constraint Satisfaction Requires Large LP Relaxations

arXiv: https://arxiv.org/abs/1309.0563 · HTML: https://mlsanity.com/paper/1309.0563/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Sep 2013.

## Built on by (most cited first, 1 of 1)

- [Efficient Symbolic Reasoning for Neural-Network Verification](https://mlsanity.com/paper/2303.13588/) (2023)

## Abstract (arXiv)

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for Max Cut has an integrality gap of 1/2 and any such linear program for Max 3-Sat has an integrality gap of 7/8.