Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{\Omega (1)}$-rounds of the Sherali-Adams linear progr…