期刊
JOURNAL OF THE ACM
卷 62, 期 2, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2716307
关键词
Theory; Combinatorial optimization; linear programming; communication complexity; semidefinite programming; quantum communication complexity
类别
资金
- Actions de Recherche Concertees (ARC) fund of the French community of Belgium
- European Commission [255961, 600700]
- Netherlands Organization for Scientific Research (NWO)
- ERC Consolidator grant QPROGRESS
We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据