Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
复制标题
DOI：
10.1145/3055399.3055438
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
Pravesh Kothari;Raghu Meka;P. Raghavendra
中科院分区：
文献类型：
--
作者：
Pravesh Kothari;Raghu Meka;P. Raghavendra
我们表明，对于约束满意度问题（CSP），子指数尺寸线性编程松弛与Sherali-Adams线性编程层次结构的nΩ（1）折叠一样强大。对许多CSP的猜测（例如最大值）和最大3SAT的线性编程放松。下限是n中的准多项式（Chan，Lee，Raghavendra，Steurer，2013年）。是“高渗透矩形”的新结构结果，可能对通信复杂性产生独立的兴趣。
We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as nΩ(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, the best known lower bounds were quasi-polynomial in n (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.