[Colloquium] [Theory] UC Theory Seminar

[Donna Brooms via Colloquium]

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar

Tuesday, November 22, 2016
Ryerson 251 @ 3 pm

Speaker: Pravesh Kothari 
(Princeton University)

Title: Approximate Constraint Satisfaction Requires Sub-exponential Size Linear Programs

Abstract: 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 programming hierarchy. As a corollary, we obtain 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].
Our bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The main ingredient in our results is a new structural result on “high-entropy rectangles” that may of independent interest in communication complexity.

Based on joint work with Raghu Meka and Prasad Raghavendra.

Host: Prof. Madhur Tulsiani
Refreshments prior to the talk in Ry. 255 @ 2:30 pm

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161111/91c71d08/attachment.html>