期刊
SIAM JOURNAL ON COMPUTING
卷 51, 期 2, 页码 -出版社
SIAM PUBLICATIONS
DOI: 10.1137/17M1152966
关键词
extended formulations; nonnegative rank; communication complexity; rectangles; juntas; lifting theorems
资金
- NSF [CCF-1408643, CCF-1343104, CCF-1553605]
- Sloan Fellowship
This study shows that weakly exponential size linear programming relaxations for constraint satisfaction problems (CSPs) are as powerful as the explicit linear program of the Sherali-Adams linear programming hierarchy. By combining with known lower bounds, subexponential size lower bounds for linear programming relaxations are obtained, which surpass random guessing for many CSPs.
We show that for constraint satisfaction problems (CSPs), weakly exponential size linear programming relaxations are as powerful as the explicit linear program described by n(Omega(1))-rounds of the Sherali-Adams linear programming hierarchy. Combining with the known lower bounds on the Sherali-Adams hierarchy, we obtain subexponential 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(o(log n)) cannot beat random guessing for such CSP Chan et al. [FOCS 2013, IEEE, Piscataway, NJ, 2013, pp. 350-359]. 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 be of independent interest in communication complexity.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据