# Approximate constraint satisfaction requires large LP relaxations

with Siu On Chan, James R. Lee, Prasad Raghavendra. FOCS 2013.

PDF

Invited to FOCS 2013 special issue, Accepted to JACM

## abstract

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 MAXCUT has an integrality gap of $\frac12$ and any such linear program for MAX 3-SAT has an integrality gap of $\frac78$.

## keywords

• strong relaxations
• lower bounds
• linear programming
• constraint satisfaction problems