Approximating CSPs requires sub-exponential size linear programs
Raghu Meka · Open Collections · 2017
We show that linear programming relaxations need sub-exponential size to beat trivial random guessing for approximately satisfying constraint satisfaction problems. In fact, we show that for such problems sub-exponential size relaxations are as powerful as n^(Omega(1))-rounds of Sherali-Adams hierarchy. Previously, only super-polynomial (~ n^(Omega(log n)) bounds were known any CSP [CLRS13]. Our bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The core of our results is a new decomposition theorem for "high-entropy rectangles" into structurally nice distributions and may be of independent interest in communication complexity. Joint work with Pravesh Kothari and Prasad Raghavendra.