CATS-Feb-17-2017
Title
Approximate Constraint Satisfaction Requires Sub-exponential Size Linear Programs
Abstract
This talk is about investigating the power of linear programming relaxations for solving constraint satisfaction problems. The main result is 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 programming hierarchy. As a corollary, this yields sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results; previously, it was only known that linear programs of size ~n^{(log n)} cannot beat random guessing for any CSP [Chan-Lee-Raghavendra-Steurer 2013]. The lower bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The main ingredient is in a new structural result on “high-entropy rectangles” that may be of independent interest in communication complexity.
Based on joint work with Raghu Meka and Prasad Raghavendra.
Bio
Pravesh Kothari is a Research Instructor in the Department of Computer Science at Princeton University and a member of the School of Mathematics at the Institute for Advanced Study. He is also a part of the Simons Algorithms and Geometry Collaboration . Previously, he received my PhD from UT Austin advised by Adam Klivans and Bachelor's degree from IIT Kanpur advised by Surender Baswana.