Abstract
We show that no polynomial-sized linear programming relaxation can achieve better than a 1/2-approximation for MAX-CUT, a 7/8-approximation for MAX-3SAT, or a 3/4-approximation for MAX-2SAT.
This is accomplished by bringing together two formerly disparate lines of research. On the one hand, there has been a recent sequence of exciting lower bounds on the size of extended formulations for various polytopes that arise in combinatorial optimization. At the same time, researchers have extensively studied the power of specific LP hierarchies for approximating NP-hard problems. We show that for max-CSP problems, general polynomial-sized LPs are exactly as power as LPs arising from a constant number of rounds of the Sherali-Adams hierarchy.
Joint work with Siu On Chan, Prasad Raghavendra, and David Steurer.