  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.
