Lower Bounds for Clique vs. Independent Set
Lower Bounds for Clique vs. Independent Set
复制标题
集团与独立集的下界
DOI：
10.1109/focs.2015.69
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Mika Göös
中科院分区：
文献类型：
--
作者：
Mika Göös
我们证明了Yannakakis （STOC 1988, JCSS 1991）引入的Clique vs. Independent Set问题的Conon确定性通信复杂度的一个ω(log n)下界。作为一个推论，这暗示了图论中Alon - Saks - Seymour猜想的超多项式下界。我们的方法是首先展示UP与coNP问题的决策树模拟的查询复杂性分离-即明确的DNF宽度与CNF宽度-然后使用先前工作的结果将这种分离“提升”到通信复杂性。
We prove an ω(log n) lower bound on the Conon deterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies super polynomial lower bounds for the Alon - Saks - Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity separation for the decision tree analogue of the UP vs. coNP question - namely, unambiguous DNF width vs. CNF width - and then "lift" this separation over to communication complexity using a result from prior work.
相关多胞形的可拓复杂度呈指数增长的简短证明
影响因子：
0.8
作者：
Volker Kaibel;Stefan Weltge
通讯作者：
Stefan Weltge