BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Approximating CSPs requires sub-exponential size linear programs Meka, Raghu

Description

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.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International