CATS-Feb-17-2017
Title[edit]
Approximate Constraint Satisfaction Requires Sub-exponential Size Linear Programs
Abstract[edit]
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[edit]
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.
