<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><div style="text-align: left;" class=""><b style="font-family: LucidaGrande; background-color: rgba(255, 255, 255, 0);" class=""><u class="">REMINDER:</u></b></div><div style="text-align: center;" class=""><b style="font-family: LucidaGrande; background-color: rgba(255, 255, 255, 0);" class=""><u class=""><br class=""></u></b></div><div style="text-align: center;" class=""><b style="font-family: LucidaGrande; background-color: rgba(255, 255, 255, 0);" class=""><u class="">Departments of Computer Science & Mathematics</u></b></div><div class="" style="text-align: center; font-family: LucidaGrande;"><span style="background-color: rgba(255, 255, 255, 0);" class=""><b class=""><u class="">Combinatorics & Theoretical Seminar</u></b></span></div></div><div class=""><div style="font-family: LucidaGrande;" class=""><br class=""></div><div style="font-family: LucidaGrande;" class=""><br class=""></div><div style="font-family: LucidaGrande;" class="">Tuesday, November 22, 2016</div><div style="font-family: LucidaGrande;" class="">Ryerson 251 @ 3 pm</div><div style="font-family: LucidaGrande;" class=""><br class=""></div><div style="font-family: LucidaGrande;" class="">Speaker: <b class="">Pravesh Kothari </b></div><div style="font-family: LucidaGrande;" class="">(Princeton University)</div><div style="font-family: LucidaGrande;" class=""><br class=""></div><div style="font-family: LucidaGrande;" class=""><span style="font-size: 12.800000190734863px;" class="">Title: Approximate Constraint Satisfaction Requires Sub-exponential Size Linear Programs</span><br class="gmail-m_4827095062818533991gmail_msg" style="font-size: 12.800000190734863px;"><br class="gmail-m_4827095062818533991gmail_msg" style="font-size: 12.800000190734863px;"><span style="font-size: 12.800000190734863px;" class="">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^{</span><span class="gmail-m_4827095062818533991inbox-inbox-s1" style="font-size: 12.800000190734863px;">(log n)} </span><span style="font-size: 12.800000190734863px;" class="">cannot beat random guessing for any CSP [</span><span class="gmail-m_4827095062818533991inbox-inbox-s2" style="font-size: 12.800000190734863px;">Chan-Lee-Raghavendra-Steurer 2013</span><span style="font-size: 12.800000190734863px;" class="">].</span><p class="gmail-m_4827095062818533991inbox-inbox-p1" style="font-size: 12.800000190734863px;">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.</p><div style="font-size: 12.800000190734863px;" class="">Based on joint work with Raghu Meka and Prasad Raghavendra.</div><div style="font-size: 12.800000190734863px;" class=""><br class=""></div><div style="font-size: 12.800000190734863px;" class=""><div style="font-size: 12.800000190734863px;" class="">Host: Prof. Madhur Tulsiani</div><div style="font-size: 12.800000190734863px;" class="">Refreshments prior to the talk in Ry. 255 @ 2:30 pm</div><div class=""><br class=""></div><div class=""><br class=""></div></div><div style="font-size: 12.800000190734863px;" class=""><br class=""></div></div></div></body></html>