Approximate Constraint Satisfaction Requires Large LP Relaxations

Siu On Chan, James R. Lee, Prasad Raghavendra +1

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…